# Tag Info

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
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 ...
• 8,553

### 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
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
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
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
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

• 17.6k
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
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

### 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

### 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
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

### 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 ...

### 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-...

### 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
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 - \...
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
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

### 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

### 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
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 (...

### 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
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