Optimization with the constraint of rank=1

Question

I have the following matrix

$$ A = [x_1, x_2, ..., x_n], $$

where $x_i \in \mathbb R^n$. But I know the relationship that

\begin{align} x_2 = s_2 x_1 \\ x_3 = s_3 x_3 \\ ... \end{align}

where $s_i$ are the scalars. So the matrix $A$ should have the rank 1.

In this case, it seems that I can decompose $A=SVD$ and truncate the other singular values except for the largest singular value and return back. So it is similar to PCA. I'm not sure this is the right approach. Could you give any comments?

Edit:

I have an objective function like this:

\begin{align} \min_x & f(x_1, x_2, ..., x_n) \\ \text{s.t. } & \operatorname{rank}([x_1, x_2, ..., x_n])=1 \end{align}

where $f$ is differentiable and I can easily use gradient descent. One simple way I thought is to apply gradient descent to $f$ and project the solution onto the rank=1 matrix. (It can be called projected gradient descent or proximal gradient descent).

Answer 1

You can parameterize your rank-1 matrix $A$ as

$A=xs^{T}$

where $x$ and $s$ are the unknown $n$ by $1$ column vectors. You then have an unconstrained problem

$\min f(x,s)$.

Depending on the function $f$, it may or may not be easy to express $f$ as $f(x,s)$ rather than as $f(A)$, and $f(x,s)$ might or might not be (probably not in practice) a convex function of $x$ and $s$.

Or, you can try to work directly with $f(A)$. However, the constraint

$\mbox{rank}(A)=1$

is a non-convex constraint. If you apply gradient descent to $f(A)$ with some kind of projection to enforce $\mbox{rank}(A)=1$, then you won't be able to obtain anything better than a local minimum.