Minimizing $\|Ax\|_2$ subject to $\|x\|_2 = 1$

Question

I have a Matlab program to estimate a vector $x$ from noisy measurements. I use the singular value decomposition (SVD) to solve the linear equation $Ax=0$ (where the number of equations is greater than the number of variables). I have read before (link below) that in this case, the solution will be the last column in the $V$ matrix (assuming [U,S,V] = svd(A) and $\|x\|=1$).

The problem is that when I test the program using true values of the measured quantities (quantities without noise) the estimated vector is correct. However, when I add the noise, the estimated vector has values which are far from the true ones (the estimated vector seems to have some of its signs converted "flipped" which makes the difference between it and the true vector large!)

I will be grateful if someone could help me.

http://andrew.gibiansky.com/blog/mathematics/cool-linear-algebra-singular-value-decomposition/

Answer 1

SVD inherently has sign ambiguity, so you will need to use some auxiliary information to resolve the direction of the vector.

You may find this answer helpful: https://mathoverflow.net/questions/41756/making-matlab-svd-robust-to-transpose-operation

This paper defines a convention for identifying the true direction of the vectors. https://www.researchgate.net/publication/227677444_Resolving_the_sign_ambiguity_in_the_singular_value_decomposition

Answer 2

As I understand the problem is: find a vector $x$ such that $||Ax||_2$ is minimized under constaint $||x||_2 = 1$ for $m\times n$ matrix A.

Such problem always has solution, but solution need not be unique.

First we need to observe that $\min ||Ax||_2 = \sigma_{min}$, where $\sigma_{min}$ is the smallest eigenvalue. Let $U$, $S$, $V$ be the SVD factorization of $A$, i.e. $USV' = A$, $S$ is the diagonal matrix of size $n\times n$ containing singular values sorted decreasingly. The vector $x$ is given by the last column of $V$. To see this observe that $V'x = e_n$, where $e_n$ is the last column of $n\times n$ identity matrix. Then $Se_n = \sigma_{min} \times e_n$, and finally $Ax = \sigma_{min} U_n$, where $U_n$ is the last column of $U$. Thus $||Ax||_2 = \sigma_{min} ||U_n||_2 = \sigma_{min}$.

Hence, the last column of the matrix $V$ is one of the solution $x$ to the problem. The second one is $-x$. There may exist other solution if the matrix $A$ has many singular values equal to $\sigma_{min}$.

Singular value decomposition is not determined uniquely. If $i$-th column of $U$ and $V$ are multiplied by -1 in the same time, then we stil have valid SVD decomposition. When the matrix $A$ is perturbed slightly, then $U$ and $V$ matrices can change dramatically, but not the S matrix.

Basically there are two solution to the problem (ignoring degenerate cases). In order to define unique solution to the problem one must impose additional constraints like for example element with maximum absolute value must be positive.

Answer 3

We would like to minimize $\|Ax\|_2$ subject to the equality constraint $\|x\|_2 = 1$. Hence,

$$\begin{array}{ll} \text{minimize} & \|Ax\|_2\\ \text{subject to} & \|x\|_2 = 1\end{array}$$

which can be rewritten as a quadratically constrained quadratic program (QCQP)

$$\begin{array}{ll} \text{minimize} & \|Ax\|_2^2\\ \text{subject to} & \|x\|_2^2 = 1\end{array}$$

Thus,

$$\|Ax\|_2^2 = x^T A^T A x \geq \lambda_{\min} (A^T A) \|x\|_2^2 = \lambda_{\min} (A^T A) = \sigma_{\min}^2 (A)$$

and

$$\|Ax\|_2 \geq \sigma_{\min} (A)$$

If $A$ has full column rank, then its SVD is of the form

$$A = U \Sigma V^T = \begin{bmatrix} U_1 & U_2\end{bmatrix} \begin{bmatrix} \hat\Sigma\\ O\end{bmatrix} V^T$$

where the zero matrix may be empty. The eigendecomposition of $A^T A$ is, thus,

$$A^T A = V \Sigma^T U^T U \Sigma V^T = V \Sigma^T \Sigma V^T = V \hat\Sigma^2 V^T$$

In this case, $\sigma_{\min} (A) > 0$, and the minimum is attained at the intersection of the $1$-dimensional vector subspace spanned by the right singular vector associated with $\sigma_{\min} (A)$ with the unit Euclidean sphere. As the singular values are usually listed in descending order, this right singular vector should be the last column of $V$. If the minimum singular value has multiplicity greater than $1$, then the minimum is attained at the intersection of a vector subspace of dimension greater than $1$ with the unit Euclidean sphere, which means that columns of $V$ other than the last could be used.

If $A$ does not have full column rank, then its SVD is of the form

$$A = U \Sigma V^T = \begin{bmatrix} U_1 & U_2\end{bmatrix} \begin{bmatrix} \hat\Sigma & O\\ O & O\end{bmatrix} \begin{bmatrix} V_1^T\\ V_2^T\end{bmatrix}$$

where the zero matrices may be empty. The eigendecomposition of $A^T A$ is, thus,

$$A^T A = V \Sigma^T U^T U \Sigma V^T = V \Sigma^T \Sigma V^T = \begin{bmatrix} V_1 & V_2\end{bmatrix} \begin{bmatrix} \hat\Sigma^2 & O\\ O & O\end{bmatrix} \begin{bmatrix} V_1^T\\ V_2^T\end{bmatrix}$$

In this case, $\sigma_{\min} (A) = 0$, and the minimum is attained at the intersection of the null space of $A$ with the unit Euclidean sphere. As the columns of $V_2$ span the null space of $A$, any column of $V_2$ would do.