# Linear regression with $n<p$: Solution of $Ax=b$ that minimizes the $2$-norm of $x$

Consider a full-rank $n\times p$ matrix $A$ and $b\in\mathbb{R}^p$. If $n<p$, I want to minimize the norm $||x||^2=x_1^2+\dots+x_p^2$ over $x\in\mathbb{R}^p$, subject to the condition $Ax=b$.

So, since $n<p$ there is not a unique solution to $Ax=b$ and we want to find the smallest one. Also, the condition $Ax=b$ is equivalent to $(A^TA)x=A^Tb$.

I have been trying to use Lagrange multipliers to solve this problem, but get stuck. Is that not the right way, or are there other better ways to do this?

• I'm pretty sure a "full [column] rank" matrix $A$ doesn't exist for $n <p$ - the best you can hope for is for rank $n$ – probabilityislogic Jul 17 '17 at 22:41

To put this in Lagrange multiplier form, this is

$$f(x) = \lVert|x\rVert^2 + \sum_{i = 1}^n\left[ \lambda_i \left( a_i x - b_i \right) \right] ,$$

where $a_i, b_i$ are, respectively, the $i$th row and element of $A, b$.

Then

$$\frac{\partial}{\text{d} x_j} f = 2x_j + \sum_{i = 1}^n \left[ \lambda_i a_{i, j} \right] = 0, (1)$$

and, of course, $$Ax = b \; (2)$$ (formally by differentiating by the $\lambda_i$).

Putting (1) in vector form,

$$2x + A^t \lambda = 0, (3)$$

where $\Lambda = [\lambda_1, \ldots, \lambda_n]$.

Combining (1) and (3), $$\begin{bmatrix} A & 0 \\ 2I & A^t \end{bmatrix} \begin{bmatrix} x \\ \lambda \end{bmatrix} = \begin{bmatrix} b \\ 0 \end{bmatrix} .$$

Assuming this can be solved, the answer is the first $n$ components of

$$\begin{bmatrix} A & 0 \\ 2I & A^t \end{bmatrix} ^{-1} \begin{bmatrix} b \\ 0 \end{bmatrix} .$$

• Yes, and this is precisely where I get stuck. – arni Jul 16 '17 at 9:23
• @arni But assuming the left matrix is $U$, and the vector on the right is $y$, then this is the first $n$ components of $U^{-1} y$. What else is there to solve? – Ami Tavory Jul 16 '17 at 9:26
• I guess I had issues with the invertibility of $U$. But from (3) we have $x=-A^t\lambda/2$, plugging into (2) gives $\lambda=-2(AA^t)^{-1}b$, so $x=A^t(AA^t)^{-1}b$, $AA^t$ being invertible because of the full rank assumption. – arni Jul 16 '17 at 20:26

This is given by using the pseudo inverse of the design matrix $x=A^{+}b$ and can be derived by considering the limit of minimising $f (x)=(b-Ax)^T (b-Ax) + kx^Tx$ as $k\to 0$.