Questions tagged [least-squares]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
12
votes
2answers
2k views

Newton-based methods in optimization vs. solving systems of nonlinear equations

I asked for clarification about a recent question about minpack, and got the following comment: Any system of equations is equivalent to an optimization problem, which is why Newton-based methods ...
12
votes
2answers
4k views

Solving a least squares problem with linear constraints in Python

I need to solve \begin{alignat}{1} & \min_{x}\|Ax - b\|^2_{2}, \\ \mathrm{s.t.} & \quad\sum_{i}x_{i} = 1, \\ & \quad x_{i} \geq 0, \quad \forall{i}. \end{alignat} I think it is a ...
11
votes
3answers
1k views

Least squares approximation question

I am taking a course on scientific computation, and we just went over least squares approximation. My question is specifically about approximating using polynomials. I understand that if you have n+1 ...
11
votes
1answer
1k views

Purely rotational least squares match

Could anyone recommend a method for the following least-squares problem: find $R \in \mathbb{R}^{3 \times 3}$ that minimizes: $\sum\limits_{i=0}^N (Rx_i - b_i)^2 \rightarrow \min$, where $R$ is a ...
8
votes
1answer
5k views

Fitting one set of points to another by a rigid motion

I'm not really sure how to explain this problem clearly, so please bear with me. I have a basis of 3 orthonormal unit vectors and a position, a standard 4x4 transform matrix in computer graphics. ...
7
votes
2answers
6k views

Least Squares and Fourier Series

I have a little bit of problem figuring out the relation between Fourier series and Least Squares. As far as I understand, LS is a way of minimizing the quadratic error between a measured value $y_i$ ...
7
votes
1answer
203 views

Least Squares with Dense-Block Diagonal Structure

I need to solve a least squares problem that takes the following form: $$p = \arg \min_{x}\Vert J V x - y \Vert_2, $$ where $J \in \mathbb{R}^{N \times N}$ is a general dense matrix, and $V \in \...
7
votes
0answers
99 views

“Geometry of ill-conditioning” for least-squares problems

It is an idea that dates back to Demmel, 1987 that the condition number of a problem is often related to the distance to the closest ill-posed problems. In Section 3 of the above paper, the author ...
6
votes
3answers
442 views

How to solve a small least-squares problem

This question is not very deep. Suppose I have a small rectangular matrix $A$, with number of rows and columns between $50$-$100$, respectively. Given a right-hand side $b$, I want to solve the least-...
6
votes
4answers
1k views

parameters estimation

I have to estimate a parameter (K), but I don't know how I can do it. I think by a regression model (minimum least square?), but I'm not sure. The system is: ...
6
votes
1answer
250 views

Proving convergence of adaptive finite elements - min res FEM?

There's a body of work out there dealing with the discrete convergence of adaptive finite element methods using error estimators. Most deal with proving the property $\|u-u_{k+1}\|_U \leq (1-\alpha) \...
5
votes
3answers
930 views

Least Squares: Numerically, is solving normal equations okay for nice matrices?

I have to solve a least squares problem: $$ x=\arg \min\|Ax-b\| $$ where $A$ is a $m\times n$ matrix, $m>n$, and $b\in\mathbb{R}^m$. I always thought that doing this via QR factorization is ...
5
votes
2answers
2k views

How to determine whether two cylinders intersect or not?

Considering any two cylinders, defined as: the center of their bottoms $A_i$, the radius of their bottom $R_i$, the unit vector $W_i$ of their axis direction, and the length $L_i$ of the cylinders, ...
5
votes
1answer
107 views

Large scale triangular least squares

I have to solve the following least squares problem: \begin{equation} \| \left[ \begin{smallmatrix} \mathbf{L} \\ \mathbf{I} \end{smallmatrix} \right]\mathbf{x} - \mathbf{b} \|_2^2 \end{equation} ...
5
votes
1answer
146 views

Pseudoinverse of perturbed matrix

How does the pseudo inverse of a full column rank matrix change if I rescale a single row? In more detail the problem is the following: We have a fixed matrix $V$ with linear independent columns and ...
4
votes
2answers
188 views

treating “almost linear” nonlinear least-squares problems

As a model for a nonlinear least-squares problem with a large linear part problem, consider $$ \Delta u = 0 \quad\text{in } \Omega,\\ n\cdot\nabla u = 0 \quad \text{on } \Gamma,\\ (u(x_i) - u(y_i))^2 =...
4
votes
1answer
72 views

Method to Efficiently Solve “Centered” Least Squares without centering “A”

Suppose I want to solve $$\text{arg min}_x \frac{1}{2}\|\tilde{A}x - b\|_2^2 + \frac{1}{2}\|x - c\|_2^2$$ where $A$ is a wide sparse matrix and $\tilde{A} = A C_n = A (I - \mathbf{1}\, \mathbf{1}^T/...
4
votes
1answer
82 views

Does the covariance matrix in Least Squares depend upon the input data?

I had always assumed that the covariance matrix depends upon the amount and quality of your input data, but I am finding out that this is not the case. Is this true? We want to fit $f(t) = \Sigma_{i=...
4
votes
1answer
191 views

How to solve the following Frobenius norm-minimization problem?

Background We know how to solve the following minimization problem $$ \min_{X} \lVert AX - B \rVert_F^2 $$ But what about the extended version? $$ \min_{X} \lVert A \begin{bmatrix} X & X^2 \...
4
votes
1answer
117 views

Nonlinear least-squares solvers vs. generic minimization

A nonlinear least-squares problem with $F:\mathbb{R}^m\to\mathbb{R}^n$, $$ F(x) \to \min_x \quad (\text{in the least-squares sense}) $$ really means minimizing $$ \frac{1}{2} \|F(x)\|^2 \to \min_x. $$ ...
4
votes
1answer
179 views

Best solver/preconditioner for least-squares finite element method

I have seen a lot of literature, lecture videos, etc. on solvers/preconditioners for non-symmetric and/or indefinite systems. However, now I want to solve the mixed poisson/Darcy equation using the ...
4
votes
2answers
570 views

Complex least-squares problem

Having a matrix $\mathbf{A} \in \mathcal{C}^{m\times n}$ I solve following least-squares problem $$Re(\mathbf{A}^H \mathbf{A})x=Re(\mathbf{A}^H\mathbf{b}).$$ If the matrix $\mathbf{A}$ was a real ...
4
votes
1answer
157 views

Factorization for reweighted least squares

I am solving a problem using an iteratively-reweighted least squares method: http://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares Essentially this requires solving a number of least-...
4
votes
0answers
39 views

Nonlinear least squares optimized Jacobian calculation

I have a nonlinear least squares problem, in which I am trying to minimize residuals which can be divided into four classes: $$ \min_x ||\epsilon(x)||^2 + ||\xi(x)||^2 + ||\delta(x)||^2 + ||s(x)||^2 $$...
4
votes
0answers
116 views

Solve ill-posed linear system without transposing matrices?

I am attempting to use an iterative solver to solve $p$ in $$ Jp = -r $$ where $J$ is an $m\times m$ matrix. Unfortunately, this is an ill-posed problem and possibly infinite versions of $p$ exist. ...
4
votes
0answers
1k views

Using MINPACK for curve fitting: implementation?

I need to implement a non-linear fitting algorithm in Fortran and chose to use MINPACK's flavor of the Levenberg-Marquardt algorithm as a basis for the least-squares stuff. However, I seem to ...
3
votes
1answer
957 views

solving a linearly-constrained sparse linear least-squares problem

[ question reposted from https://math.stackexchange.com/questions/786612/solving-a-linearly-constrained-sparse-linear-least-squares-problem ] Given the system of equations $Ax=b$, subject to $Cx\le ...
3
votes
1answer
264 views

Large-scale box-constrained linear least-squares

I need to solve $$\mbox{min}||Ax - b||_2^2 \quad \mbox{s.t.} \quad l \leq x \leq u,$$ where $A \in R^{m \times n}$, $m \ll n$, $n \approx 10^4-10^5$. BVLS [1] based on active-set method works fine ...
3
votes
1answer
83 views

Nonlinear least squares when some parameters are linear

Consider the least squares problem, $$ \min_{\mathbf{a},\mathbf{b}} || \mathbf{f}(\mathbf{a},\mathbf{b})||^2 $$ where $\mathbf{a},\mathbf{b}$ represent the unknown parameters to be found. In my ...
3
votes
1answer
194 views

How to solve the inverse problem of least-squares?

Focusing on following least squares problem: $$\min\limits_{V} \lVert Z - WV \rVert _{_F}^2$$ $$Z∈{R}^{m\times n},\quad W∈{R}^{m\times k},\quad V∈{R}^{k\times n},\quad k\lt m\lt n $$ This problem ...
3
votes
1answer
124 views

Obtaining a feasible solution for underdetermined system of linear equations satisfying inequality constraints

I would like to obtain a feasible solution for an under-determined system of linear equations, $$Ax=b$$ where, $A \in \mathbb{R}^{7\times9}, \, x \in \mathbb{R}^{9\times1}\text{and } b\in\mathbb{R}^...
3
votes
1answer
73 views

Solving multiple least-square problems with the same constraints

The following least-square problem can be solved efficiently (e.g. using matlab's lsqlin): $$\vec{x}^*=\arg\min_\vec{x} ||C\vec{x}-\vec{t}||^2\,\ s.t.\ Ax \le \vec{b}$$ where the parameters of the ...
3
votes
1answer
457 views

indirect method for least-squares with inequality constraints

I aim to find $x \in \mathbb{R}^n$ that $\min_x |D \cdot F \cdot x|^2$ subject to $x_i = X_i$ and $x_j \geq X_j$ , $i \in I, j \in J$ and I and J partition ${1\cdots N}$ into two sets. it is ...
3
votes
1answer
197 views

How do you formulate the linear least-squares method for radiometric calibration?

In Debevec and Malik (mentioned similarly in Forsyth and Ponce's Computer Vision: A Modern Approach) they highlight a method of solving the camera response function using linear least-squares. We ...
3
votes
0answers
126 views

Nonlinear least squares and regularization

Consider the nonlinear least-squares minimization of a vector of $n$ residuals $\mathbf{f}$ in $p$ parameters $\mathbf{x}$: $$ \min_{\mathbf{x}} || \mathbf{f}(\mathbf{x}) ||^2 $$ This can be done with ...
3
votes
0answers
36 views

Reweighted least squares factorization

This is a continuation of the question asked here. I want to solve numerous least squares systems of the form $$ D_i A x \approx D_i b $$ where $D_i$ are $m \times m$ diagonal matrices with positive ...
3
votes
0answers
76 views

Backward stable algorithm to get orthogonal projection onto the column space of a matrix

I have to find the orthogonal projection of a vector $b$ onto the matrix $A$ of size $m \times n$. In my application, I don't have the luxury of calculating the QR factorization. All I have are ...
3
votes
0answers
1k views

Polynomial Fitting with Least Squares using Numpy and Scipy

I am trying to fit data to a polynomial using Python - Numpy. The points, with lines sketched above them are as in the picture. I am trying to fit those points to a polynomial of 4. or 5. degree. ...
2
votes
2answers
1k views

Solving non-negative least squares in Matlab (by analogy with least squares)

There is a least-squares problem. It can be solved using backslash in Matlab. If Ax = b, then x = A \ b. Let's assume that I ...
2
votes
2answers
127 views

efficient mean of solving constrained OLS problems?

I was wondering whether there was a efficient procedure for solving constrained quadratic approximations of the form: $$\underset{k\in \mathbb{R}}{\min}\;||x_i-kx_0||_2$$ for fixed values of $x_0,...
2
votes
1answer
85 views

Description of algorithm for small scale linear least squares with box constraints

I have small scale dense least squares problem with box constraints $$\mbox{argmin}||Ax - b||^2 \quad $$ $$\mbox{subject to} \quad l_i \leq x_i \leq u_i,$$ Number of variables is about 10-50, ...
2
votes
1answer
103 views

Parameter reduction algorithm for least square model

Question I am performing least squares fitting using an objective function of the form $f(\mathbf{x})$ where $\mathbf{x}$ is a vector of parameters containing around 20 elements. The model function ...
2
votes
1answer
202 views

Projecting onto convex shapes - best fit convex polygon

I am interested in studying a problem of the form $\min F(\Omega)$ where $\Omega$ varies in the class of convex, open sets in the plane. An idea is to deform $\Omega$ at each step using a steepest ...
2
votes
1answer
105 views

Formulation of the least-squares parameter estimation problem

I have a system of 10 ordinary differential equations of the form, $$\frac{dy_1}{dt} = f1(V1,k1,y1,y2)\\ \vdots \\ \frac{dy_{10}}{dt} = f_{10}(V_{10},k_{10},y_{9},y_{10}) $$ I want to estimate the ...
2
votes
1answer
122 views

Solving sparse least squares system with limited memory

This was a question on a past final that we can't figure out. Take the least squares system $$\min_x ||Ax-b||_2\, ,$$ where $A\in\mathbb{R}^{mxn}$, $m<n$, and A is full rank. A has $\mathcal{O}(n)...
2
votes
1answer
243 views

Minimizing Cost Functions using Iterative Least Squares

I am currently trying to use iterative least squares to solve a system, $y = Hx + v$ where $y$ is a vector of observations, $H$ is the design matrix, and $v$ is the observation error. From my ...
2
votes
1answer
942 views

Solve Regularized Least Squares problems using Matlab optimization toolbox

I am trying to solve a least squares problem where the objective function has a least squares term along with L1 and L2 norm regularization. I am unable to find which matlab function provides the ...
2
votes
0answers
30 views

Fitting a plane with the Prewitt gradient operator

Prewitt gradient operator Show that the Prewitt gradient operator can be obtained by fitting the least-squares plane through the 3 × 3 neighborhood of the intensity function. Hint: Fit a plane to ...
2
votes
0answers
74 views

Regularized least squares with QR factorization

Consider the regularized least squares problem $$ \min_x || b - A x ||^2 + \lambda^2 ||x||^2 $$ which is equivalent to $$ \min_x \left|\left| \pmatrix{b \\ 0} - \pmatrix{A \\ \lambda I} x \right|\...
2
votes
0answers
269 views

Convergence of a very large non-linear least squares optimization

(note: I also posted this question on stackoverflow before finding this community here, which seems a better place for it) I'm trying to solve the following problem: I have a lot (~80000) surface ...