# Optimization with the constraint of rank=1

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).

• The title mentions optimisation, but i don't see an optimisation problem in your question. I'm assuming that $A$ is the contraint matrix, but i think it would help if you wrote out the actual problem. – Thijs Steel Jan 3 '20 at 13:58
• That's the very good point. I've added some more contexts. Hope it clarifies more! – jakeoung Jan 3 '20 at 18:15
• Can you explicitly show us what the function $f$ is? I presume you know the $s_i$ exist, but don't know their numerical values? What exactly do you know about them? – Mark L. Stone Jan 3 '20 at 18:24

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.