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?

  • $\begingroup$ 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 $ $\endgroup$ – 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$.


$$ \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} . $$

  • $\begingroup$ Yes, and this is precisely where I get stuck. $\endgroup$ – arni Jul 16 '17 at 9:23
  • $\begingroup$ @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? $\endgroup$ – Ami Tavory Jul 16 '17 at 9:26
  • $\begingroup$ 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. $\endgroup$ – 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$.


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.