Tag Info

Accepted

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 ...
• 11.6k

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,340
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,143

• 18.8k
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 ...
• 18.8k
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 ...
• 18.8k

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 ...
• 10.3k
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 ...
• 11.6k

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 ...
• 55.8k

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 ...
• 55.8k
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 ...
• 55.8k
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 ...
• 18.8k
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 ...
• 11.6k
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 ...
• 18.8k

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-...
• 2,821

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-...
• 18.8k

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

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,239
Accepted

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 $\... • 18.8k 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 ... • 55.8k 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 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 ... • 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 ... • 55.8k 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]$. • 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^...
• 11.6k
In a comment you state that the condition number of the system of the normal equentions is as small as $\kappa=5$. For such a well condtioned problem it might be a good idea to try the conjugate ...