Least squares problem with constraint on the unit sphere It is easy to find the minimum of $\|Ax-b\|_2$, when $A$ has full column rank. But how is the case when we add the constraint $\|x\|_2=1$? Or, to be explicit,
$$\min_{\|x\|_2=1}\|Ax-b\|_2=?$$
My idea is to construct the corresponding Lagrange function
$$L(x,\lambda) = (Ax-b)^T(Ax-b) + \lambda(x^T x - 1)$$
Differentiate the function with respect to $x,\lambda$, we have
$$A^T A x - A^T b + \lambda x = 0$$
$$x^T x=1$$
However, I find it hard to move forward to get the answer. Could anyone help me? Thanks a lot!
 A: Note that if you solve for:
$$
\min ||Ax - b||^2_2\\
s.t. ||x||^2_2 =1
$$
then you have a QCQP program with one quadratic constraint. You can solve for this in polynomial time, since strong duality applies, see here at equation 5 for a list of references for this problem.
A: Differentiation of $L$ gives me
$$ 2A^T A x - (A + A^T)b + 2\lambda x = 0, $$
using that $(x^T A^T A)^T = A^T A x$. You also get $x^T x = 1$, of course. Now, you have
$$ (A^T A + \lambda I)x = \frac{1}{2} (A+A^T)b, $$
and somehow have to get to an equation for $x$ and $\lambda$. Obvious thing to try: dot with the significant vectors in the problem, $x$ and $b$, which gives
$$ x^T A^T Ax + \lambda = \frac{1}{2} b^T(A+A^T)x = \frac{1}{2}(b^T A x + x^T A b) \\
b^T A^T A x + \lambda b^T x = \frac{1}{2}b^T (A+A^T)b = b^T A b $$
Then, assuming that $A^T A + \lambda I$ is invertible (we'll have to sort this out later, but it seems plausible for now), we have
$$ x = \frac{1}{2}(A^T A +\lambda I)^{-1}(A+A^T)b. $$
Inserting this in $x^T x =1$ gives
$$ 4 = b^T (A+A^T)^2(A^T A + \lambda I)^{-2} b, $$
using that $A+A^T$ and $A^T A + \lambda I$ are symmetric and commute. Unfortunately I don't think this equation is easy to solve at all, even for simple matrices: you get a polynomial in $\lambda$ of degree $2n$, $n$ the dimension. Of course, should anyone prove this wrong I'd be quite pleased. Geometrical considerations show that the minimum should exist and be unique, however: you're looking the smallest size of ellipse with matrix $A$ centred at $b$ that intersects the unit sphere. Or use the convexity.
