18
votes
Accepted
Least squares approximation question
The most important aspect of interpolation and curve fitting is to understand why high order polynomial fits can be an issue and what the other options are and then you can understand when they are/...
- 4,521
8
votes
Accepted
Reverse-engineering a quadratic fit?
My first guess was that they computed a minimax best-approximation polynomial to $\sqrt{x}$ on [0,5,1] with something like the Remez algorithm. However, plotting the difference $p(x)-\sqrt{x}$ I do ...
- 8,553
7
votes
Least Squares: Numerically, is solving normal equations okay for nice matrices?
For solving the least squares problem in general as principal methods there are (matrix $A$ with full rank):
solve the system of normal equations $A^{T}Ax = A^{T}b$
use QR factorization
use SVD ...
- 1,300
6
votes
Accepted
Least Squares and Fourier Series
In a word, yes.
A least squares problem arises in the context of an over determined system. That means that you have more equations than unknowns and would be the case if you had more data points ...
- 4,521
6
votes
Accepted
How to determine whether two cylinders intersect or not?
David Eberly has a good description of the solution (with pseudocode) here: http://www.geometrictools.com/Documentation/IntersectionOfCylinders.pdf
The short summary: like most convex-convex ...
- 331
6
votes
Accepted
treating "almost linear" nonlinear least-squares problems
If you change variables to optimize for the residual of the linear part, then the Hessian will be a low-rank update to the identity. Then L-BFGS would work very well. Specifically, your problem takes ...
- 3,003
5
votes
Accepted
Does the covariance matrix in Least Squares depend upon the input data?
I can't quite read your notation, but suppose we tried to find a set of parameters $x$ that give rise to predictions $y(x)=Ax$ by comparing with measurements $\bar y$. Then, if you try to find your ...
- 50.2k
5
votes
Finding parameters numerically
In general, you can formulate this as a nonlinear least squares problem. If your values are known at points $(x_{i},y_{i})$, and the known values are $f_{i}$, then you can minimize
$\min_{a,b,c,d,e} ...
- 17.6k
5
votes
Accepted
Nonlinear least-squares solvers vs. generic minimization
If we let
$\phi(x)=\sum_{i=1}^{m} F_{i}(x)^{2}$,
we could compute $\nabla \phi(x)$ by finite difference approximation. However, it is generally smart to make use of the special structure of $\phi(...
- 17.6k
5
votes
Accepted
Method to Efficiently Solve "Centered" Least Squares without centering "A"
How would you solve the problem if you didn't need to do the centering?
Since $A$ is large and sparse, you'd probably pick an iterative method such as CGNE which depends on being able to perform ...
- 17.6k
5
votes
Accepted
Fastest algorithm for pseudoinverse of skinny matrices
If $A$ is of full column rank and $A^{T}A$ is non-singular and well-conditioned, then you can compute the pseudoinverse as:
$ A^{\dagger}=(A^{T}A)^{-1}A^{T} $.
This will be faster than computing a ...
- 17.6k
5
votes
Cholesky decomposition vs LDL decomposition
As the commenters have already said, for your specific problem, QR factorization might be a better approach not because of speed but because of numerical stability.
It's still a good question to ask ...
- 8,087
4
votes
Least Square fit with Double Zernike Polynomials
If I read this correctly, you can rewrite your problem as an ordinary least square problem $\left\|Ax-b\right\|$, where A is the stacked Vandermonde-Matrix of the derivatives of the Zernike ...
- 1,285
4
votes
Accepted
Optimisation of purely integer quantity with bound-constraints for a 1D expensive function whose analytical form is not available
@Stellos already gave the correct answer, but let me try to back it up with a bit of intuition:
Think of your function $f(x)$ as a function that would actually make sense for any real-valued argument ...
- 50.2k
4
votes
Large scale triangular least squares
This looks isomorphic to Tikhonov regularization (a.k.a. ridge regression). Some googling brought up LSQR and the newer LSMR. Those links both have implementations in a number of languages. For ...
- 473
4
votes
Efficient methods to solve large dense singular least square problem (linear system)
Pretty sure that what you want is Non-negative least squares. Plenty of implementations already exist, so you shouldn't have to write any code to get going. https://en.wikipedia.org/wiki/Non-...
- 51
4
votes
treating "almost linear" nonlinear least-squares problems
If you want to solve such problems with least squares, you need to first address two things:
You are interested in a continuous problem, not one particular discretization of it. Your statement "quite ...
- 50.2k
4
votes
Accepted
How to solve the following Frobenius norm-minimization problem?
$$\big\| \mathrm A \begin{bmatrix} \mathrm X & \mathrm X^2\end{bmatrix} - \begin{bmatrix} \mathrm B_1 & \mathrm B_2\end{bmatrix} \big\|_{\text{F}}^2 = \underbrace{\| \mathrm A \mathrm X - \...
4
votes
Accepted
Update for QR factorization least squares
SYRK is not really relevant here I think; it is just something else that happens to have the same name "rank k update".
In your case, you need to know how to ...
- 8,553
4
votes
Accepted
L1 least squares minimization with a sparse matrix
If you have a good LP solver, then the linear programming approach often works well. You don’t want to implement your own simplex or interior point code for LP though.
A specialized variant of the ...
- 17.6k
4
votes
Sparse least squares with a (black-box) ill-conditioned operator
There's no reason to compute elements of $M=A^{*}A$ here. You will need the ability to compute the adjoint operator $z \rightarrow A^{*}z$. With that, you can use a matrix-free iterative least-...
- 17.6k
3
votes
Efficient methods to solve large dense singular least square problem (linear system)
You could try my MATLAB solver PDCO which uses an interior method and will be happy that your n < m.
Use
options.Method = 1 % the default
d1 = 1e-4
d2 = 1
3
votes
Accepted
Parameter reduction algorithm for least square model
I'll add a real response here, following the comment I just left. As @GeoffOxberry suggests, you might be able to use active subspaces to, in essence, preprocess your objective function and eliminate (...
3
votes
How to determine whether two cylinders intersect or not?
Hint:
If the two cylinders are parallel, the problem is easy. Otherwise, if the perpendicular distance between the axis exceeds the sum of the radii, there is no intersection.
Otherwise, there is an ...
- 128
3
votes
Accepted
Projecting onto convex shapes - best fit convex polygon
The set of convex sets is infinite dimensional, which is not amenable to computation. I would discretize this by replacing your solution set (consisting of all convex sets) by a finite dimensional set ...
- 50.2k
3
votes
Accepted
solving a linearly-constrained sparse linear least-squares problem
If you have access to the MATLAB optimization toolbox then this can easily be done using the quadprog() function. You'd start by writing the objective in quadratic form as
$ \| Ax - b \|_{2}^{2} = ...
- 17.6k
3
votes
Accepted
Description of algorithm for small scale linear least squares with box constraints
You should take a look at the excellent book by Nocedal and Wright on "Numerical Optimization". It has a great deal of material on these kinds of problems.
The algorithm you refer to, where one only ...
- 50.2k
3
votes
Linear Least-Squares Point-to-Plane ICP degenerative case
This approach is the result of a Taylor approximation, which assumes that we are not very far from the solution (solution is the case when $R\approx I$ - no more updates can be made). Under large ...
- 2,139
3
votes
Accepted
Pivoted Cholesky vs Modified Cholesky
Neither of these approaches is recommended. Although pivoted Cholesky factorization can help with badly conditioned matrices, it ultimately won't help with a singular matrix. The modified Cholesky ...
- 17.6k
3
votes
What is a good library in Python for correlated fits in both the $x$ and $y$ data?
Here is the current code I am using to do correlated fits in the $x$ and $y$ directions. I wrote it from this reference. I adapted it from section 1.A.i and 4.B
...
- 311
Only top scored, non community-wiki answers of a minimum length are eligible