Least squares with an equality constraint

Question

For the following problem :

$$ \begin{aligned} & \min _{\mathbf{x} \in \mathbb{R}^n}\|\mathbf{y}-\mathbf{A} \mathbf{x}\|_2^2 \\ & \text { subject to } \mathbf{q}_1^T \mathbf{x}=1 \end{aligned} $$ where $\mathbf{A} \in \mathbb{R}^{m \times n}$ has full column rank, and $\mathbf{q}_1 \in \mathbb{R}^n$ has $\left\|\mathbf{q}_1\right\|_2=1$. Use LS to show that the solution to the above problem is $$ \mathbf{x}^*=\mathbf{q}_1+\mathbf{Q}_2\left(\mathbf{Q}_2^T \mathbf{A}^T \mathbf{A} \mathbf{Q}_2\right)^{-1} \mathbf{Q}_2^T \mathbf{A}^T\left(\mathbf{y}-\mathbf{A} \mathbf{q}_1\right) $$ where $\mathbf{Q}_2 \in \mathbb{R}^{n \times(n-1)}$ is any matrix such that $\left[\begin{array}{ll}\mathbf{q}_1 & \mathbf{Q}_2\end{array}\right]$ is an orthogonal matrix. $

I have used the Lagrange Multiplier technique to obtain

$$L(x,\lambda) = \lVert y-Ax \rVert^2 + \lambda(q_1x-1)$$

$$\nabla_xL(x,\lambda) = \lambda q_1 - 2A^Ty-2A^TAx$$ $$\nabla_\lambda L(x,\lambda) = q_1 - 1 $$

According to KKT they have to be equal to zero to obtain a set of Linear system of equations

\begin{equation} \begin{bmatrix} 2A^TA & q_1 \\ q_1 & 0 \end{bmatrix} \begin{bmatrix} x_1\\ \lambda \end{bmatrix} = \begin{bmatrix} 2A^Ty\\ 1 \end{bmatrix} \end{equation}

Solving for $x_1$ we get

$$ x = (A^TA)^{-1}(A^Ty - \lambda q_1/2) $$

using the fact that $$q_1 x = 1$$

$$q_1 x = 1$$ $$q_1 (A^TA)^{-1}(A^Ty - \lambda q_1/2) = 1$$

$$q_1 (A^TA)^{-1}A^Ty -q_1 (A^TA)^{-1} \lambda q_1/2 = 1$$

$$ q_1 (A^TA)^{-1} \lambda q_1 *(1/2) = -(1-q_1 (A^TA)^{-1}A^Ty)$$

$$ \lambda = -2(q_1 (A^TA)^{-1} q_1)^{-1}(1-q_1 (A^TA)^{-1}A^Ty)$$

but obviously this is wrong since these matrices are not invertible, where I am I going wrong any help is greatly appreciated.

Answer 1

We can express x as a combination of two matrices:

$$x = q_1 + Q_2 z $$

where $z$ is a (n-1)-dimensional vector. We can substitute this expression for x into the constraint $q_1^T x = 1$: $$ q_1^T (q_1 + Q_2 z) = 1 $$ which simplifies to:

$$ q_1^T q_1 + q_1^T Q_2 z = 1 $$ since $\lVert q_1\rVert = 1$ and $[q_1 Q_2]$ is an orthogonal matrix, we have $q_1^T Q_2 = 0$, so the above equation becomes $q_1^T q_1 = 1$. Therefore we need not have the constraint now.

Substitute the expression for x into the objective function:

$$\lVert y - A(q_1 + Q_2 * z)\rVert ^2 $$ $$= \lVert y - Aq_1 - AQ_2z\rVert ^2 $$ $$= (y - Aq_1 - AQ_2z)^T (y - Aq_1 - AQ_2z) $$ $$= y^T y - 2y^T Aq_1 - 2z^T Q_2^T A^T y + q_1^T A^T A q_1 + z^T Q_2^T A^T A Q_2 z - 2q_1^T A^T A Q_2 z $$ We want to minimize this expression with respect to z. Taking the derivative with respect to z and setting it equal to zero, we get:

$$-2Q_2^T A^T y + 2Q_2^T A^T A Q_2 z - 2q_1^T A^T A Q_2 = 0 $$ Multiplying both sides by $(Q_2^T A^T A Q_2)^{-1}$, we get: $$ z = (Q_2^T A^T A Q_2)^{-1} Q_2^T A^T (y - Aq_1)$$

Substituting this expression for z into the expression for x, we get: $$ x = q_1 + Q_2 (Q_2^T A^T A Q_2)^{-1} Q_2^T A^T (y - Aq_1) $$

Answer 2

Here is a different approach to the problem.

Recall the linearly constrained linear least-squares problem and its solution $$\eqalign{ \def\LR#1{\left(#1\right)} \def\op#1{\operatorname{#1}} \def\trace#1{\op{Tr}\LR{#1}} \def\frob#1{\left\| #1 \right\|_F} \def\o{{\tt1}} \def\m#1{\left[\begin{array}{r}#1\end{array}\right]} \def\qiq{\quad\implies\quad} \min_x\:&\frob{Ax-y}^2 \\ \op{s.t.}\:&Bx=z \\ &P = \LR{I - B^+B},\quad P^2=P=P^T,\quad BP=0 \\ &x = B^+z + P\LR{AP}^+\LR{y-AB^+z} \\ }$$ Here $B^+$ denotes the pseudoinverse of $B,\:$ and $P$ is a projector into the nullspace of $B$.

Mapping these variables to the current problem $$\eqalign{ &z = q_1^Tq_1 = \m{\o},\quad B = q_1^T,\quad &B^+ = q_1,\quad P = \LR{I - q_1q_1^T} \\ }$$ yields $$\eqalign{ x &= q_1 + P\LR{AP}^+\LR{y-Aq_1} \\ }$$ Comparing this to the solution using semi-orthogonal $Q_2$
(re-written using pseudoinverse notation) $$\eqalign{ x &= q_1 + Q_2\LR{AQ_2}^+\LR{y-Aq_1} \\ }$$ one sees that the form of the solutions is the same, however the $Q$-solution depends on the existence of $\LR{A^TA}^{-1}$ whereas the $P$-solution does not.