Questions tagged [least-squares]

Questions about (linear or nonlinear) least-squares, an estimation method used in statistics, signal processing and elsewhere.

Filter by
Sorted by
Tagged with
14
votes
3answers
4k views

How does the SVD solve the least squares problem?

How do I prove that the least-squares solution for $$\text{minimize} \quad \|Ax-b\|_2$$ is $A^{+} b$, where $A^{+}$ is the pseudoinverse of $A$?
4
votes
2answers
2k views

What forms does the Moore-Penrose inverse take under systems with full rank, full column rank, and full row rank?

The normal form $ (A'A)x = A'b$ gives a solution to the least square problem. When $A$ has full rank $x = (A'A)^{-1}A'b$ is the least square solution. How can we show that the moore-penrose solves ...
8
votes
3answers
3k views

Least squares Problem with Non Negativity Constraints

Let $\mathbf{x}=[x_1,\ldots,x_K]$. I have the following optimization problem: \begin{array}{rl} \min \limits_{\mathbf{x}} & \| \mathbf{Ax}-\mathbf{b} \|^2 \\ \mbox{s.t.} & x_k\ge 0, \forall ...
3
votes
2answers
1k views

Closed Form Solution of $ \arg \min_{x} {\left\| x - y \right\|}_{2}^{2} + \lambda {\left\|x \right\|}_{2} $ - Tikhonov Regularized Least Squares

The problem is given by: $$ \arg \min_{x} \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \lambda {\left\|x \right\|}_{2} $$ Where $y$ and $x$ are vectors. $\|\cdot\|_2$ is Euclidean norm. In the ...
-2
votes
1answer
847 views

Singular value decomposition proof

I need help in the following question. I'm not sure how to even begin to answer this. What is a possible proof for the following question? If $A$ is an $m \times n$ matrix and $b$ is an $m$-vector, ...
5
votes
3answers
8k views

Difference between orthogonal projection and least squares solution

When you find the least squares solution you solve $$A^TA = A\vec b$$ but to find the orthogonal projection into the "subspace" A, you multiply this result (the least squares solution) with the ...
14
votes
3answers
17k views

Derivative of squared Frobenius norm of a matrix

In linear regression, the loss function is expressed as $$\frac1N \left\|XW-Y\right\|_{\text{F}}^2$$ where $X, W, Y$ are matrices. Taking derivative w.r.t $W$ yields $$\frac 2N \, X^T(XW-Y)$$ Why ...
11
votes
1answer
3k views

Orthogonal Projection of $ z $ onto the Affine set $ \left\{ x \mid A x = b \right\} $

Suppose $A$ is fat(number of columns > number of rows) and full row rank. The projection of $z$ onto $\{x\mid Ax = b\}$ is (affine) $$P(z) = z - A^T(AA^T)^{-1}(Az-b)$$ How to show this? ...
5
votes
3answers
10k views

Unique least square solutions

There is a theorem in my book that states: If $A$ is $m\times n$, then the equation $Ax = b$ has a unique least square solution for each $b$ in $\mathbb{R}^m$. But can we find a counter-example to ...
19
votes
4answers
24k views

Why does SVD provide the least squares and least norm solution to $ A x = b $?

I am studying the Singular Value Decomposition and its properties. It is widely used in order to solve equations of the form $Ax=b$. I have seen the following: When we have the equation system $Ax=b$, ...
12
votes
3answers
20k views

Difference between least squares and minimum norm solution

Consider a linear system of equations $Ax = b$. If the system is overdetermined, the least squares (approximate) solution minimizes $||b - Ax||^2$. Some source sources also mention $||b - Ax||$. If ...
13
votes
4answers
7k views

Matrix Calculus in Least-Square method

In the proof of matrix solution of Least Square Method, I see some matrix calculus, which I have no clue. Can anyone explain to me or recommend me a good link to study this sort of matrix calculus? ...
2
votes
3answers
6k views

Least Square Approximation for Exponential Functions

I'm a little confused on how to approach the following problem. Use the least square method to fit a curve of the form $y=a\cdot b^x$ to a collection of $n$ data points $(x_1,y_1),...,(x_n,y_n)$ ...
1
vote
1answer
842 views

Is the unique least norm solution to $Ax=b$ the orthogonal projection of b onto $R(A)$?

True or false: The unique least norm solution to $Ax=b$ is the orthogonal projection of b onto $R(A)$ So, first isn't this the definition of least squares? The only incorrect thing I can think of is ...
0
votes
3answers
169 views

Solve Linear Least Squares Problem with Unit Simplex Constraint

$$ \min_x ||Ax - b||_2\; \;\text{given }x \geq 0\;\;\text{and}\;\;\textbf{1}^Tx = 1 $$ I am trying to do the above optimization, I was using common Quadratic programming libraries but their speed is ...
12
votes
3answers
950 views

Solve Least Squares Minimization from Over Determined System with Orthonormal Constraint

I would like to find the rectangular matrix $X \in \mathbb{R}^{n \times k}$ that solves the following minimization problem: $$ \mathop{\text{minimize }}_{X \in \mathbb{R}^{n \times k}} \left\| A X - ...
6
votes
2answers
3k views

Comparing LU or QR decompositions for solving least squares

Let $X \in R^{m\times n}$ with $m>n$. We aim to solve $y=X\beta$ where $\hat\beta$ is the least square estimator. The least squares solution for $\hat\beta = (X^TX)^{-1}X^Ty$ can be obtained ...
6
votes
1answer
7k views

Linear Least Squares with Linear Inequality Constraints

I'm trying to follow this older paper, page 19. The goal is to solve: $\min \|Ax-b\|^2 s.t. Gx \ge h$ given $A, G, b, h$ By combining the equations into a single LCP of the form: $Mz + q = w$ s.t. $...
4
votes
3answers
466 views

Explain why $x^+=A^+b$ is the shortest possible solution to $A^TA\hat{x}=A^Tb$

I'm was going through the chapter on pseudoinverse in intro to linear algebra by Strang, and it says The vector $x^+=A^+b$ is the shortest possible solution to $A^TA\hat{x}=A^Tb$ Reason: The ...
3
votes
2answers
1k views

Why is minimizing least squares equivalent to finding the projection matrix $\hat{x}=A^Tb(A^TA)^{-1}$?

I understand the derivation for $\hat{x}=A^Tb(A^TA)^{-1}$, but I'm having trouble explicitly connecting it to least squares regression. So suppose we have a system of equations: $A=\begin{bmatrix}1 &...
2
votes
1answer
2k views

Exact solution of overdetermined linear system

Given a (possibly) overdetermined linear system $Ax=b$, where $A$ is full rank and $A \in \mathbb{R}^{m \times n}, \quad m \ge n$ Does the least squares method provide an exact solution (instead of ...
1
vote
2answers
454 views

Least squares and pseudo-inverse

Let $b\in \mathbb{R}^m$,$A\in M_{m\times n}(\mathbb{R})$ with $m>n$ and $rank(A)=n$, and the element $x^*\in \mathbb{R}^m$ solution of least squares of $Ax=b$. i) Show that $r^*=b-Ax^*\in N(A^T)$ ...
3
votes
2answers
2k views

Is a least squares solution to $Ax=b$ necessarily unique

Let $A$ be an $m$ x $n$ matrix, and suppose that $b\in\mathbb{R}^n$ is a vector that lies in the column space of $A$. Is a least squares solution to $Ax=b$ necessarily unique? If so, give a detailed ...
5
votes
5answers
15k views

Proof of convexity of linear least squares

It's well known that linear least squares problems are convex optimization problems. Although this fact is stated in many texts explaining linear least squares I could not find any proof of it. That ...
9
votes
0answers
275 views

How do you solve linear least-squares modulo $2 \pi$?

I have an overdetermined system of $m$ equations ($i = 1, 2, \dots, m$) $$ \sum_{j=1}^n A_{ij} \, x_j = y_i \pmod{2\pi} $$ where the $x$ coefficients are unknown, and $m > n$. This is basically the ...
5
votes
4answers
2k views

Matrix Linear Least Squares Problem with Diagonal Matrix Constraint

How could one solve the following least-squares problem with Frobenius Norm and diagonal matrix constraint? $$\hat{S} := \arg \min_{S} \left\| Y - XUSV^T \right\|_{F}^{2}$$ where the $S$ is a ...
6
votes
3answers
1k views

Why does $A^TAx = A^Tb$ have infinitely many solution algebraically when $A$ has dependent columns?

This is a problem from least square approximation, where we solve the equation $A^TAx = A^Tb$ when $Ax = b$ is unsolvable. The case I am dealing with is when A has dependent columns, i.e. A is an m by ...
3
votes
3answers
4k views

Is the pseudoinverse matrix the solution to the least squares problem?

I'm trying to verify that, given a matrix M, the pseudo-inverse $$M^{+}=(M^TM)^{-1}M^T$$ is the solution for the least squares.. but something went wrong and I can't undestand why... $$e=\frac{1}{2}||...
5
votes
2answers
5k views

Show that the least squares line must pass through the center of mass

My problem: The point $(\bar x, \bar y)$ is the center of mass for the collection of points in Exercise 7. Show that the least squares line must pass through the center of mass. [Hint: Use a change ...
3
votes
2answers
2k views

Solving Linear Least Squares with Linear Inequality Constraints

Given: $$ \begin{aligned} A \in \mathbb{R}^{m \times n} \\ y \in \mathbb{R}^{m \times 1} \\ c, d \in \mathbb{R}^{m \times 1} \\ d \geq c \geq 0 \\ y \geq 0 \end{aligned} $$ I seek $\hat{x}$: $$ \...
3
votes
1answer
287 views

Least squares invariant under transformation?

Suppose that $\hat{x}$ is the least squares solution of $Ax = b$. That is, $\min{|r|}, r = Ax - b$ with respect to $x$. Is $\hat{x}$ also the least squares solution of $JAx = Jb$? I suspect so, but ...
2
votes
2answers
5k views

Underdetermined Linear Systems and the Least Squares Solution

I have an underdetermined linear system, with 3 equations and four unknows. I also know an initial guess for these 4 unknows. The article I am reading says: We can solve the system using the least ...
2
votes
3answers
4k views

Solving $Ax=b$ when $x$ and $b$ are given.

I am trying to study least square and linear regression and I understand the solution for $Ax = b$ when x is the unknown and the LS solution is given by $(A^TA)^{-1}A^TA$. Now, I was wondering if ...
1
vote
1answer
1k views

Solution to least squares problem using Singular Value decomposition

Let $A_{mn}$, $m\geq n$ have full column rank and $A=U_1 \Sigma V^T$ be its reduces singular value decomposition. Show that the linear least squares problem $min_{x \in R^n} \||y-Ax||_2$ is solved at $...
4
votes
3answers
794 views

If $A$ is a non-square matrix with orthonormal columns, what is $A^+$?

If a matrix has orthonormal columns, they must be linearly independent, so $A^+ = (A^T A)^{−1} A^T$ . Also, the fact that its columns are orthonormal gives $A^T A = I$. Therefore, $$A^+ = (A^T A)^{−1}...
3
votes
4answers
5k views

How come least square can have many solutions?

I know there always exists a least-square solution $\hat{x}$, regardless of the properties of the matrix $A$. However, I keep finding online that least-square can have infinitely many solutions, if $A$...
3
votes
3answers
204 views

Best fitting in a curve of the form $Ax^B+C$

I am trying to fit data of the form $(x_i,y_i)$, $i=1,\ldots,n$, in a curve of the form $y=Ax^B+C$, where $B\in (0,1)$. All three constants $A,B,C$ are to be determined optimally (no particular norm ...
2
votes
2answers
842 views

Finding the null space of a matrix by least squares optimization?

I've had some idea I could do something like this: $${\bf v_o}=\min_{\bf v} \{\|{\bf M(v+r)}\|_2^2 + \epsilon\|{\bf v}\|_2^2\}$$ for a random vector $\bf r$ and then $\bf v$ should point in the ...
1
vote
2answers
96 views

Least Square fit for signal data (360 points)

I would like to analyze data to get the maximum value out of 360 points. I used least square fitting because I get the data from signal strengths. I want to remove any outliers I get from my data ...
1
vote
2answers
1k views

Solving least squares problem using partial derivatives

Let's say we want to solve a linear regression problem by choosing the best slope and bias with the least squared errors. As example, let the points be $x=[1, 2, 3]$ and $y=[1,2,2]$. This quadratic ...
1
vote
1answer
2k views

Complex ($\mathbb C$) least squares derivation

I know how to derive the least squares in the real domain. If a tall matrix $A$ and a column vector $b$ are real, then the solution of the least squares problem $Ax = b$ can be derived as: $$\begin{...
1
vote
1answer
568 views

Least Squares with Unit Simplex Constraint Variation

I have to solve the following least square problem: $$\hat{x} = \arg \min_{x \in S} \|Ax - b\|^2$$ If $S = \mathbb{R}^n$, then the solution is given by $$\hat{x} = (A^TA)^{-1}A^Tb$$ supposing that ...
1
vote
1answer
99 views

What parameters can be used to tell a least squares fit is “well fit”?

A least squares fit to data gives an equation but how can I tell if the created equation fits into data "well"? I thought of using residuals between data and the equation but is there a more general ...
1
vote
2answers
155 views

Proof of the normal equations theorem

Thm: Let the minimization problem be: $$ \min_{y \in \mathbb{R}^{n}}{\| Ay - b\|_{2}^{2}} = \| Ax - b\|_{2}^{2}$$ the problem admits a solution if and only if: $$ A^{\mathrm{ T }}Ax = A^{\mathrm{ ...
1
vote
2answers
255 views

How does minimum squared error relate to a linear system?

Given some system $U*x = b$, I've solved for $x^*$, the least squares solution. I then compute the minimum squared error by $||U*x^* - b||^2$. I know that the least squares solution minimizes the ...
1
vote
2answers
151 views

Least squares problem: find the line through the origin in $\mathbb{R}^{3}$

The problem is as follows: "Please set up (but do not solve) the normal equations for the following least squares approximation problem: Find $(a, b, c, d)$ such that the plane H described by $ax + ...
0
votes
1answer
208 views

How to Solve Linear Least Squares with Unit Simplex Constraint

How to minimize the follow optimization $$\begin{array}{ll} \text{minimize} & \| \mathbf{A}\mathbf{x} - \mathbf{b} \|^2\\ \text{subject to} & {\mathbf{x}}^{T} \mathbb{1} = \mathbb{1}\\ & \...
0
votes
2answers
516 views

Solver for Norm Constraint Least Squares

I'm looking for a numerical solution to the constrained least squares problem below: $$ \min_\mathbf{x}\|\mathbf{a+Bx}\|^2 ~~\text{s.t}~~\|\mathbf{x}\|^2 \leq \alpha^2$$ where $\mathbf{a} \in \mathbb{...
-2
votes
1answer
118 views

How to Solve Linear Least Squares Problem with Box Constraints [closed]

How could one solve the following Least Squares with Box Constraints problem: $$\begin{aligned} \arg \min_{x \in \mathbb{R}^{n}} \quad & \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} \\ \text{...
6
votes
1answer
5k views

Analytic solution for matrix factorization using alternating least squares

The standard form for ridge regression aims to minimize the following cost function. $$ \min\ \ \sum_i(y_i-x_i^T\beta)^2 + \lambda\sum_j\beta^2_j $$ As described here, it's possible to differentiate ...