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 ...
Federico Poloni's user avatar
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 ...
Mauro Vanzetto's user avatar
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 ...
Nick Alger's user avatar
  • 3,143
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} ...
Brian Borchers's user avatar
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 ...
Brian Borchers's user avatar
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(...
Brian Borchers's user avatar
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 ...
Brian Borchers's user avatar
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 ...
Daniel Shapero's user avatar
5 votes
Accepted

Measuring the extent to which two sets of vectors span the same space

The classical tool for this job is canonical angles. The canonical angles between $\operatorname{Im} A$ and $\operatorname{Im} B$ can be computed as $\arccos \sigma_i$, where $\sigma_i$ are the ...
Federico Poloni's user avatar
5 votes

Spot redundant equations within nonlinear system of equations

In the example you give, the two equations are not redundant. Each of the two equations describes a set of lines in the 2d plane, and the lines happen to be tangential at a specific point -- which is ...
Wolfgang Bangerth's user avatar
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 ...
Wolfgang Bangerth's user avatar
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 ...
Wolfgang Bangerth's user avatar
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-...
user1337732's user avatar
4 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 ...
Brian Borchers's user avatar
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 ...
Federico Poloni's user avatar
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 ...
Brian Borchers's user avatar
4 votes

Reverse-engineering a quadratic fit?

If my computer history is not wrong, no one would use the initial guess obtained from the quadratic polynomial you provided and use the algorithm you suggested. This is due to two reasons: floating-...
Abdullah Ali Sivas's user avatar
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-...
Brian Borchers's user avatar
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
Michael Saunders's user avatar
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 ...
Tolga Birdal's user avatar
  • 2,229
3 votes
Accepted

Solving for $C$ in $Q = YCZ$ using least squares in Matlab

You can reformulate this problem as a conventional linear least squares problem as follows: First, write $YCZ$ as $YCZ=\sum_{i=1}^{p} \sum_{j=1}^{m} C_{i,j} (Y_{:,i}Z_{j,:})$ Next, define the $\...
Brian Borchers's user avatar
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 ...
Wolfgang Bangerth's user avatar
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 ...
kηives's user avatar
  • 311
3 votes
Accepted

Complexity of solving an image differential linear system

TL;DR For an image of size $m\times n$ you can solve this problem in $O(nm(\log(n) + \log(m)))$. In fact, there is nothing to "solve", the solution can be written down analytically. The ...
Amit Hochman's user avatar
  • 1,081
3 votes

How can we solve the normal equations with limited memory?

That might also have been a trick question. Let's say you want to solve the normal equations for $Ax=b$, i.e., $(A^T A) x = A^T b$. Let's assume for a moment that the questioner meant that $A$ is ...
Wolfgang Bangerth's user avatar
3 votes

Reverse-engineering a quadratic fit?

This polynomial $p(x)$ solves the minimax optimization for $$\frac{p(x)}{\sqrt{x}}-1$$ over the interval $[\tfrac12,1]$.
WimC's user avatar
  • 131
3 votes
Accepted

Finding best phase in least-squares manner

It seems to me that you can't do any better than taking the classical least-squares solution $x = A^+y$. To see that, replay the solution of the least-squares problem via SVD: take an SVD $A=U\Sigma V^...
Federico Poloni's user avatar
2 votes
Accepted

How to code gradient descent-based Tikhonov denoising that exactly matches LSQ Tikhonov denoise?

There are a few problems with your gradient descent: The gradient of $\|\nabla u\|^2$ is $$\nabla^* \nabla u = -\mathrm{div} \nabla u = -\Delta u,$$ i.e., the negative Laplacian. Gradient descent ...
Christian Clason's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible