Minimization of Least squares $ \left\| v - b \right\|$ With Linear Constraint Where $ b\in \ker A $

Question

Let $$A=\begin{pmatrix}5&-10&-15\\ -1&2&3\\2&-4&-6\end{pmatrix}\in \mathbb R^{3\times 3}.$$

Fix $v\in\mathbb R^3$. How can I find $$\min_{b\in \ker A}\|b-v\| \ \ ?$$

I know that I can find an orthonormal basis of $\ker A$, complete in a orthonormal basis of $\mathbb R^3$ and then take the orthogonal projection of $v$ onto $\ker A$. But I would like to use the mean square method. But I know how to use it only if I have to minimize $\min_{u\in\mathbb R^3}\|Au-c\|$ when column of $A$ are linearly independent.

Answer 1

Hint

Compute $\ker(A)$. Let say it's $Span\{v_1,v_2\}$. Then Apply the method you know with the matrix $$M=(v_1\ v_2)\in \mathcal M_{3\times 2}(\mathbb R).$$

Answer 2

$$ \ker (A) = \{(x,y,z); x=2y+3z;y,z\in \mathbb{R}\} $$ $$= \{y(2,1,0)+z(3,0,1);y,z\in \mathbb{R}\}$$

Say $v=(a,b,c)$ then with use of Cauchy-Schwarz inequality we have:

$$\begin{eqnarray}||b-v||^2 &=& (a-2y-3z)^2+(b-y)^2+(c-z)^2\\ &=& {1\over 14}(1+4+9)\Big((2y+3z-a)^2+(b-y)^2+(c-z)^2\Big)\\ &\geq & {1\over 14}\Big((2y+3z-a)+(2b-2y)+(3c-3z)\Big)^2\\ &= &{1\over 14}(-a+2b+3c)^2\\ \end{eqnarray} $$ With equality $${2y+3z-a\over 1} = {b-y\over 2} = {c-z\over 3}$$ and this is when $$y={a+5b-3c\over 7}\;\;\;{\rm and}\;\;\;z ={3a-6b+5c\over 14}$$

So $$\min_{b\in \ker A}\|b-v\| = {1\over \sqrt{14}}|-a+2b+3c|$$

Answer 3

The problem is given by:

$$\begin{align*} \arg \min_{x} \quad & \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} \\ \text{subject to} \quad & A x = \boldsymbol{0} \end{align*}$$

The Lagrangian is given by:

$$ L \left( x, \mu \right) = \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + {\mu}^{T} A x $$

The KKT System is given by:

\begin{align*} {\nabla}_{x} L \left( x, \mu \right) = x - y + {A}^{T} \mu & = 0 & \text{(1)} \\ {\mu}^{T} A x & = 0 & \text{(2)} \\ \end{align*}

Taking (1) and multiplying from left by $ A $ and remembering $ A x = 0 $:

$$ A x - A y + A {A}^{T} \mu = 0 \underset{A x = 0}{\Rightarrow} A {A}^{T} \mu = A y \Rightarrow \mu = {\left( A {A}^{T} \right)}^{\dagger} A y $$

Plugging the result into (1) yields:

$$ x - y + {A}^{T} {\left( A {A}^{T} \right)}^{\dagger} A y = 0 \Rightarrow x = y - {A}^{T} {\left( A {A}^{T} \right)}^{\dagger} A y $$

Plug in your matrix and you'll get the answer.

Answer 4

$\DeclareMathOperator{rank}{Rank} \DeclareMathOperator{image}{Image} \DeclareMathOperator{vspan}{Span}$Here's a geometric approach that exploits the fact that $\rank A = 1$.

Since $\rank A = 1$, so $\dim \ker A = 2$. Also recall that $(\ker A)^\perp = \image A^T$; that is, the kernal of $A$ is perpendicular to the rowspace of $A$. This means that for our minimizer $b^*$, we have $v = b^* + w$, where $w$ is in the row-space of $A$ and $Av = Aw$.

Since our matrix $A$ has a one-dimensional row-space $\image A^T = \vspan\{(1, -2, -3)\}$, we get the explicit formula $$w = \frac{\lVert A v \rVert}{\lVert A(1,-2,-3)\rVert} (1,-2,-3)$$ and so $$\min_{b \in \ker A} \lVert b - v \rVert = \lVert w \rVert = \lVert Av \rVert \frac{\lVert (1, -2, -3) \rVert}{\lVert A(1, -2, -3) \rVert} = \frac{\lVert Av \rVert}{7\sqrt{10}}.$$

---

The method in this anwser can be generalized to argue that $$\min_{b \in \ker A} \lVert b - v\rVert = \min_{Aw = Av} \lVert w \rVert.$$

Since the matrix $\tilde A$ that we get from expressing $A$ as a map from $\image A^T$ to $\image A$ is invertible, our problem reduces to finding and inverting $\tilde A$. In this problem, $\tilde A$ is a $1\times 1$ matrix, so it is very easy to find the answer.