3
$\begingroup$

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 proof. If not, find a counter example.

I understand that a least-squares solution to $Ax=b$ is a vector $\hat{x}\in\mathbb{R}^n$ such that $\|b-A\hat{x}\|\le\|b-Ax\|$ for any vector $x\in\mathbb{R}^n$ which gives me the impression that the least squares solution to $Ax=b$ is not necessarily unique. However, I'm at a loss as to how to prove this.

$\endgroup$
  • $\begingroup$ Rank conditions? $\endgroup$ – user251257 Mar 29 '16 at 3:29
  • $\begingroup$ What is "Col A"? $\endgroup$ – John Hughes Mar 29 '16 at 3:30
  • $\begingroup$ @JohnHughes probably the column space of $A$ $\endgroup$ – user251257 Mar 29 '16 at 3:41
  • $\begingroup$ Well, since $b$ is in the column space of $A$, $b=Ax$ for some $x$. Hence the residual norm of the LS problem can be made zero. What happens if we add to this $x$ some $y$ such that $Ay=0$? $\endgroup$ – Algebraic Pavel Mar 29 '16 at 4:15
  • 1
    $\begingroup$ Pavel's thinking along the same lines I am. How about $A = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}, b = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, x_1 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, x_2 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$? Seems pretty non-unique. Simpler still is $A = \begin{bmatrix} 0 \end{bmatrix}, b = \begin{bmatrix} 0\end{bmatrix}, x_1 = \begin{bmatrix} 1\end{bmatrix}, x_2 = \begin{bmatrix} 2 \end{bmatrix}$. :) $\endgroup$ – John Hughes Mar 29 '16 at 11:10
3
$\begingroup$

The statement needs a crisp definition. Consider the matrix $\mathbf{A}\in\mathbb{C}^{m\times n}_{\rho}$ ($m$ rows, $n$ columns, rank $\rho$).

Uniqueness

If the data vector $b$ is not in the null space $\mathcal{N}(\mathbf{A}^{*})$ the least squares solution exists. If the number of columns is greater or equal to the rank of $\mathbf{A}$, $n\ge \rho$, the solution is unique.

Demonstration

The linear system $\mathbf{A}x=b$, $$ \begin{bmatrix}1 & 0\end{bmatrix} \begin{bmatrix}x \\ y\end{bmatrix} = \begin{bmatrix}b\end{bmatrix}, $$ offers the least squares solution $$ x_{LS} = \color{blue}{x_{particular}} + \color{red}{x_{homogeneous}} = \color{blue}{\begin{bmatrix}b \\ 0\end{bmatrix}} + \alpha \color{red}{\begin{bmatrix}0 \\ 1\end{bmatrix}} $$ where the arbitrary constant $\alpha \in \mathbb{C}$

The particular solution lives in the range space $\color{blue}{\mathcal{R}(\mathbf{A})}$. The homogeneous solution inhabits the null space $\color{red}{\mathcal{N}(\mathbf{A}^{*})}$. When this null space is trivial (when $n\ge \rho$), the is no homogeneous contribution and the least squares solution is unique.

Unique least square solutions

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

If $b$ is in the column space of $A$ then a true solution exists, which is unique if and only if the columns of $A$ are linearly independent.

If $b$ is not in the column space of $A$ then the least-squares solution is the orthogonal projection of $b$ to the column space of $A$, which is of course unique.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.