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
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$, ...
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 ...
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$?
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? ...
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 ...
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 - ...
11
votes
1answer
4k 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? ...
10
votes
2answers
21k views

simple example of recursive least squares (RLS)

I'm vaguely familiar with recursive least squares algorithms; all the information about them I can find is in the general form with vector parameters and measurements. Can someone point me towards a ...
10
votes
1answer
4k views

Tikhonov regularization vs truncated SVD

To find $\mathbf{x}$ such that $$A\mathbf{x}=\mathbf{b}$$ we can use least squares when the problem is not well posed. Further, we can use Tikhonov regularization when $A$ is ill-conditioned. In ...
9
votes
2answers
2k views

Prove that the system $A^T A x = A^T b$ always has a solution

Prove that the system $$A^T A x = A^T b$$ always has a solution. The matrices and vectors are all real. The matrix $A$ is $m \times n$. I think it makes sense intuitively but I can't prove it ...
9
votes
5answers
296 views

“Least Squares” of Dirac Delta?

It is well known that the first $N$ terms of a Fourier series of an even function $f$ corresponds to the least squares approximation of $f$ on $[-\pi,\pi]$ using the functions $S = \{1,\cos(x), \cos(...
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 ...
9
votes
1answer
126 views

Does anyone know a reference to best-fitting lines with integral coefficients?

I'm writing up a manual on how to generate "nice" Linear Algebra problems; that is, where the solutions tend to be integral. I "discovered" the following fact about the best-fitting line: Theorem. ...
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 ...
8
votes
2answers
159 views

How to solve this equation (may be with least squares)?

I have the optimization problem $$\arg\min_{a,b} \sum_{i,j} \left( \left| X(i,j)-aY(i,j)\right|-b \right)^2$$ Where $X$ and $Y$ are known. But there is a modulus inside. I need to estimate $a$ and $...
8
votes
1answer
155 views

Estimating Parameter - What is the qualitative difference between MLE fitting and Least Squares CDF fitting?

Given a parametric pdf $f(x;\lambda)$ and a set of data $\{ x_k \}_{k=1}^n$, here are two ways of formulating a problem of selecting an optimal parameter vector $\lambda^*$ to fit to the data. The ...
6
votes
4answers
3k views

Why don't $A^TAx = A^Tb$ and $Ax=b$ have the same solution?

Suppose $A$ is a $m\times n$ matrix, $x$ is a vector of unkowns and $b$ is a vector of know entries. Why don't $$Ax=b$$ and $$A^TAx = A^Tb$$ have the same solution ($x$)? It seems to me that I could ...
6
votes
3answers
515 views

Minimize $ \|A-BXC \|_F$ subject to $\mbox{rank} (X) \leq r$

I have the following problem. Let $A$, $B$ $C$ be real-valued matrices of size $m \times q$, $m \times n$, $p \times q$ respectively. Find matrix $X$ of size $n \times p$ and maximum rank $r$ ...
6
votes
3answers
3k views

Least squares / residual sum of squares in closed form

In finding the Residual Sum of Squares (RSS) We have: \begin{equation} \hat{Y} = X^T\hat{\beta} \end{equation} where the parameter $\hat{\beta}$ will be used in estimating the output value of input ...
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 ...
6
votes
2answers
7k views

Is the Square Root of an Inverse Matrix Equal to the Inverse of the Square Root Matrix?

I know in general that if a matrix $A$ is positive definite, then there exists a (unique?) square root matrix $B$, which is also positive definite, such that $BB=A$. Therefore, suppose $A$ is ...
6
votes
2answers
12k views

How to calculate the lens distortion coefficients with a known displacement vector field?

I have this vector field full of displacement vectors, which indicates radial distortions by a lens system. (Source) I know where each of the displacement vectors starts $(x,y)$ and ends $(x',y')$ ...
6
votes
4answers
182 views

Optimal rounding a sequence of reals to integers

I'm given positive real numbers $c_1,\dots,c_m \in \mathbb{R}$ and an integer $d \in \mathbb{N}$. My goal is to find non-negative integers $x_1,\dots,x_m \in \mathbb{N}$ that minimize $\sum_i (x_i - ...
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. $...
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 ...
6
votes
2answers
61 views

Where am I going wrong in calculating the projection of a vector onto a subspace?

I am currently working my way through Poole's Linear Algebra, 4th Edition, and I am hitting a bit of a wall in regards to a particular example in the chapter on least squares solutions. The line $y=a+...
6
votes
1answer
433 views

Nearest signed permutation matrix to a given matrix $A$

Let $A \in \mathbb{R}^{n\times n}$ be a square matrix and let $Q \in O(n)$ be the nearest orthogonal matrix to $A$ under the Frobenius norm, i.e. $$Q = \text{arg}\min_{M \in O(n)} ||A - M||_{F}^2$$ ...
6
votes
2answers
5k views

The SVD Solution to Linear Least Squares / Linear System of Equations

I'm a little confused about the various explanations for using Singular Value Decomposition (SVD) to solve the Linear Least Squares (LLS) problem. I understand that LLS attempts fit $Ax=b$ by ...
6
votes
2answers
371 views

$Ax=b$ is solvable, then it has the same solutions of $A^TAx=A^Tb$

I have to prove that given a matrix $A \in \mathbb{R}_{m\times n}$ and $b \in \mathbb{R}^n$. Suppose that the system $Ax=b$ is solvable, x is solution of $Ax=b$ If and only if x is solution of $A^...
6
votes
0answers
718 views

Response Surface Methodology using Moving Least Squares Method

I would like to obtain the response surface of a mathematical function for reliability-based design optimization (RBDO). To obtain a reliably response surface, I learned that moving least squares ...
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 ...
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 ...
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 ...
5
votes
3answers
1k views

Why is the denominator $N-p-1$ in estimation of variance?

I was recently going through the book Elements of Statistical Learning by Tibshirani et.al. In this book, while explaining the ordinary least squares model, the authors state that assume that $y_i \...
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 ...
5
votes
1answer
160 views

What are the connections between square integrable functions in the context of Fourier series and least squares regression?

$L^2([0,1])$ integrability is a condition to express a periodic function as a Fourier series: $$\left\vert \int_{0}^L f(x)- \int_{0}^L \sum_{k=-n}^n \hat f(k)\;\mathrm e^{\frac{2\pi}{L} kx} \right \...
5
votes
1answer
1k views

When is Block-Partitioned Matrix Invertible?

Suppose I have a block partitioned matrix \begin{equation} \begin{bmatrix} \mathbf{X}_1^{\top}\mathbf{X}_1 & \mathbf{X}_1^{\top}\mathbf{X}_2 \\ \mathbf{X}_2^{\top}\mathbf{X}_1 & \mathbf{X}_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 ...
5
votes
2answers
973 views

What is the proof that SVM can be used to solve the least squares problem with norm equality constraint?

I've seen it claimed that the solution to the minimization problem: $$\begin{align*} \arg \min_{b} \quad & {\left\| A b \right\|}_{2}^{2} \\ \text{subject to} \quad & {\left\| b \right\|}_{2} ...
5
votes
1answer
2k views

Matrix Projection onto Positive Semi Definite Cone with Respect to the Spectral Norm

A book that I am reading ("Convex Optimization" by S.Boyd and L.Vandenberghe, page 399, book pdf) states that projection of a symmetric $n\times n$ matrix $X_0$ onto the set of symmetric $n \times n$ ...
5
votes
1answer
621 views

Semidefinite relaxation for Boolean least squares

I am working on the Boolean least squares problem, which comes up a lot in circuit design. In its raw form, it looks like this $$\begin{array}{ll} \text{minimize} & \operatorname{tr}(A^TAX) - 2b^...
5
votes
3answers
3k views

How to perform a monotonic function fitting of data points?

I'm seeking suggestions for general purpose function fitting of a set of data points, where, based on physical intuition, the relationship is expected to be "monotonic", i.e. the function should be ...
5
votes
1answer
2k views

Is the Frobenius norm minimizer the same as the $2$-norm minimizer?

Given matrices $A \in \mathbb{R}^{n \times m}$ and $B \in \mathbb{R}^{n \times k}$, consider the least squares minimizer $$\arg \min_{X \in \mathbb{R}^{m \times k}} \| AX - B \|_F$$ where $\| M \|...
4
votes
3answers
2k views

Shortest distance between two lines in 3-dimensional space [closed]

Can someone explain to me how to solve this question? Find the shortest distance between the lines $L_1 = \left\{t \begin{bmatrix} 1\\ 1\\ 1\end{bmatrix} : t \in \mathbb{R}\right\}$ and $L_2 = \left\...
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 ...
4
votes
3answers
6k views

Solve an overdetermined system of linear equations

I have doubt to solve this system of equations \begin{cases} x+y=r_1\\ x+z=c_1\\ x+w=d_1\\ y+z=d_2\\ y+w=c_2\\ z+w=r_2 \end{cases} Is it an overdetermined system because I see there are more ...
4
votes
2answers
370 views

How to Solve Linear Least Squares with Matrix Inequality Constraint

I need to solve the following inequality-constrained least-squares problem in vector $x$ $$ \min_{Ax \geq 0} \frac{1}{2} \|Ax-b\|_2^2$$ where matrix $A$ and vector $b$ are given. I am totally ...
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 ...
4
votes
4answers
7k views

Find best-fit parabola to the given data

Find the parabola $At^2+Bt+C$ that best approximates the data set $t= -1,0,1,2,3$ and $b(t) = 5,2,1,2,5$. Would I be using least squares such that $x = (A^TA)^{-1}A^Tb$? Thank you in advance.

1
2 3 4 5
28