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/...
user avatar
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 ...
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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} ...
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(...
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 ...
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 ...
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
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-...
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 ...
user avatar
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 - \...
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 ...
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 ...
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-...
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
user avatar
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 (...
user avatar
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 ...
user avatar
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 ...
user avatar
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} = ...
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 ...
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 ...
user avatar
  • 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 ...
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 ...
user avatar
  • 311

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