Projection of a vector onto the null space of a matrix

Question

I have the following optimization problem: $$ \text{minimize}_x \Vert z - x \Vert^2 \\ \text{subject to } Ax = 0, $$ where $x,z\in \mathbb{C}^N$, and $A\in\mathbb{C}^{M \times N}$. $A$ is a wide matrix, i.e. $M \le N$, with rank $M$. I found a closed-form solution to this problem in "D. Bertsekas, Nonlinear Programming, 1999", which is $$ x_\star = (I_N - A^H(AA^H)^{-1}A)z, $$ where $I_N$ is the $N \times N$ identity matrix. However, I'm having problems deriving this solution.

I have tried to use the Lagrange multiplier method as follows. The dual optimization problem is $$ \text{minimize}_{\{x,\lambda\}} \Vert z - x \Vert^2 + \lambda \Vert Ax \Vert^2, $$ where $\lambda > 0$ is a Lagrange multiplier. Setting the derivative of the Lagrangian Dual with respect to $x$ to zero gives $$ x_\star = (I_N - A^HA)^{-1}z, $$ and, applying the matrix inversion lemma, I get $$ x_\star = (I_N - A^H(\tfrac{1}{\lambda}I_M + A A^H)^{-1}A)z. $$ Thus, the solution in the book and the solution I'm getting are equal when $\lambda \rightarrow \infty$. What does this mean? Any ideas how can I get the $\lambda \rightarrow \infty$ condition?

Thank you very much for your help.

Answer 1

It might be easier to use some (related) facts from linear algebra. Implicit in Bersekas' solution is the fact that $A$ has full rank, which is equivalent to $A A^*$ being invertible.

The space $\ker A$ is a (closed) subspace, and the problem is to find the nearest point in the subspace to the point $z$. It is straightforward (using a compactness argument) to show that a solution exists.

In the following, I am assuming that $A$ has full rank.

At a solution $\hat{x}$, we have $\|z-x\|^2 \ge \|z-\hat{x}\|$ for all $x \in \ker A$. Writing $\|z-x\|^2 = \|z-\hat{x}\|^2 + \|x-\hat{x}\|^2 - 2 \operatorname{re} \langle z-\hat{x}, x-\hat{x}\rangle $ and combining gives $\|x-\hat{x}\|^2 \ge 2 \operatorname{re} \langle z-\hat{x}, x-\hat{x}\rangle $, and since $\ker A$ is a subspace, this shows that $z-\hat{x} \bot \ker A$.

Since $\ker A = ({\cal R}A^T)^\bot$, we can write $z-\hat{x} = A^* \hat{y}$ for some $\hat{y}$, and since $\hat{x} \in \ker A$, we have $A z= A A ^* \hat{y}$ and since we have assumed full rank, we have $ \hat{y} = (A A ^*)^{-1} A z$, and so the solution is given by $\hat{x} = z-A^* \hat{y} = (I-A^*(A A ^*)^{-1} A)z $.

Answer 2

You are actually not using duality here. What you are doing is called (pure) penalty approach. So that is why you need to take $\lambda$ to $\infty$ (as shown in NLP by bertsekas). Here is the proper way to show this result. We want to solve $$\min_{Ax=0}\frac{1}{2}\|x-z\|_2^2$$

The Lagrangian for the problem reads $$\mathcal{L}(x,\lambda)=\frac{1}{2}\|z-x\|_2^2+\lambda^\top Ax$$ Strong duality holds, we can invert max and min and solve $$\max_{\lambda}\min_x \frac{1}{2}\|z-x\|_2^2+\lambda^\top Ax$$ Let us focus on the inner problem first, given $\lambda$ $$\min_x \frac{1}{2}\|z-x\|_2^2+\lambda^\top Ax$$ The first order optimality condition gives $$x=z-A^\top \lambda$$ we have that $$\mathcal{L}(z-A^\top \lambda,\lambda)=-\frac{1}{2}\lambda^\top (AA^\top) \lambda+\lambda^\top A z$$ Maximizing this concave function wrt. $\lambda$ gives $$(AA^\top) \lambda=Az$$ If $AA^\top$ is invertible then there is a unique solution, $\lambda=(AA^\top)^{-1}Az$, otherwise $\{\lambda | (AA^\top) \lambda=Az\}$ is a subspace, for which $(AA^\top)^{\dagger}Az$ is an element (here $\dagger$ denotes the Moonroe Penrose inverse). All in all, a solution to the initial problem reads $$x=(I-A^\top(AA^\top)^{\dagger}A)z$$

Answer 3

You can argue that as $\lambda \to \infty$ you should get the correct solution because that will force $Ax = 0$, at least in the limit, since $Ax = 0$ is possible. The fact that you get a slightly different solution for finite $\lambda$ also shows that in fact it is required to let $\lambda \to \infty$ in order to get $Ax = 0$

Answer 4

\begin{align} \min_{\bar{x}}\ ||c-\bar{x}||^2 \\ s.t.\ A\bar{x} = 0 \end{align} Objective function can be written as \begin{align} (c-\bar{x})^T(c-\bar{x})\\ c^Tc - 2 c^T\bar{x} + \bar{x}^T\bar{x} \end{align} Given that all constraints are linear, the Karush-Kuhn-Tucker conditions can be applied. \begin{align} -2c + 2x + A^Tv &= 0\\ Ax &= 0\\ 2x + A^Tv &= 2c\\ 2Ax + AA^Tv &= 2Ac\\ AA^Tv &= 2Ac\\ v &= (AA^T)^{-1}2Ac\\ -2c + 2x + A^Tv &= 0\\ -2c + 2x + A^T(AA^T)^{-1}2Ac &= 0\\ -c + x + A^T(AA^T)^{-1}Ac &= 0\\ x &= c - A^T(AA^T)^{-1}Ac\\ &= (I - A^T(AA^T)^{-1}A)c \end{align}

Answer 5

There is a problem with the optimization equation. The correct equation has to be $$\Vert x-z \Vert^2 + \lambda(Ax)$$ To make the math simpler use the slightly tweaked but similar equation $$\tfrac12\Vert x-z \Vert^2 + \lambda(Ax)$$ After differentiating the Lagrangian with respect to $x$ and $\lambda$, you get $$ \begin{bmatrix} I & A^T\\ A & 0 \\ \end{bmatrix} \begin{bmatrix} x\\ \lambda \end{bmatrix} = \begin{bmatrix} z\\ 0 \end{bmatrix} $$

Solving which, gives $$ x = ( I - A^T(AA^T)^{-1}A)z $$