# Projection of a vector onto the null space of a matrix

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.

• If $A A^*$ is to be invertible, you need $A$ to have full rank (that is $M$). – copper.hat Jun 9 '15 at 15:32
• Yes, sir. I edited the question... – CViteri Jun 9 '15 at 16:27
• Note that what you have above is not the dual problem. – copper.hat Jun 9 '15 at 16:55
• You are right. When I take the correct dual problem $$\text{minimize}_{\{x,\lambda\}} \Vert z-x \vert^2 + \lambda^H A x + x^H A^H \lambda,$$ with $\lambda \in \mathbb{C}^M$, the solution in Bertsekas is derived easily. – CViteri Jun 9 '15 at 17:58

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$$

• Thank you, your answer is very clear... – CViteri May 18 at 22:32

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

• Thank you very much for your answer. – CViteri Jun 9 '15 at 17:52
• Note that showing $z-\hat{x} \bot \ker A$ is not as immediate as the above would indicate. Let $z-\hat{x} = w + k$ where $k \in \ker A$ and $w \bot \ker A$, and choose $x = \hat{x} + {1 \over 2}k$. This will show that $k=0$. – copper.hat Jan 26 '18 at 21:34
• Curious why you unaccepted my answer after 4 years? – copper.hat May 19 at 7:43
• Hello, I read this post yesterday after a few years and the most recent answer is more clear to me – CViteri May 19 at 16:12

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$

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

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$$