# Is it possible to do rank reduction with constraints

I have a real $$n\times m$$ matrix $$\mathbf{A}=U\Sigma V^T$$ s.t. $$\operatorname{rank}(\mathbf{A})> 1$$. Let $$\mathbf{B}\in \mathbb{R}^{n\times m}$$ be the best rank-1 approximation of $$\mathbf{A}$$ that comes from singular vectors of $$\mathbf{A}$$

$$$$\mathbf{B}=\sigma_1*\mathbf{u}_1*\mathbf{v}_1^{T}$$$$

My question is:

Is it possible to find $$\mathbf{B'}\in \mathbb{R}^{n\times m}$$, defined as $$\mathbf{B'}=\mathbf{x}*\mathbf{y}^T$$, with following constraints on $$\mathbf{x},\mathbf{y}$$

1. $$\mathbf{x}\in\mathbb{R}^{n\times 1}$$ and last $$(n-n_1)$$ elements of $$\mathbf{x}$$ are $$0
2. $$\mathbf{y}\in\mathbb{R}^{m\times 1}$$ and last $$(m-m_1)$$ elements of $$\mathbf{y}$$ are $$0

$${\bf x} = \left.\left( \begin{array}{c} x_1\\ \vdots\\ x_{n_1}\\ x_{n_1+1}\\ \vdots\\ x_n \end{array} \right) \right\}n\hspace{2mm}, {\bf y} = \left.\left( \begin{array}{c} y_1\\ \vdots\\ y_{m_1}\\ y_{m_1+1}\\ \vdots\\ y_m \end{array} \right) \right\}m\hspace{2mm}$$

If yes, then what kind of optimization problem is this, convex or not? And how do I write the objective function.

Optimization cost is: $$\min\|\mathbf{B}-\mathbf{B'}\|_2$$

• Just a comment: Interestingly, even the original un-restricted problem is non-convex. To be more precise, the desired singular vectors can be computed by maximizing a convex function, which is a non-convex problem. (Alternatively, if you express the problem as minimization of the spectral or Frobenius error, you also have the rank constraint.) However, we know how to solve it efficiently. – megas Sep 27 '16 at 0:17

Some thoughts, which may not answer the question definitively.

Edit: I originally thought that we are given an arbitrary matrix $\mathbf{A}$ and we are looking for sparse (scaled) singular vectors $\mathbf{x}$ and $\mathbf{y}$, where a specific subset of entries is restricted to be in $(0, \epsilon)$. I now realize that the problem was different:

• Let $\mathbf{A}$ be a given arbitrary matrix and let $\mathbf{B} = \sigma_{1}\mathbf{u}_{1}\mathbf{v}_{1}^{\top}$ be its best rank-$1$ approximation. We seek $\mathbf{x}$ and $\mathbf{y}$ with specific restrictions, such that the matrix $\mathbf{B} = \mathbf{x}\mathbf{y}^{\top}$ is the best approximation of $\mathbf{B}^{\prime}$ (and not $\mathbf{A}$).

Note that $\mathbf{B}^{\prime}$ being the best approximation of $\mathbf{B}^{\prime}$ is not the same as being the best (constrained) approximation of $\mathbf{A}$.

Observations:

1. First assume that we are willing to force the small entries to be equal to zero.

• The problem of approximating $\mathbf{B}$ with $\mathbf{B}^{\prime}$ should be easy. Let $\overline{\mathbf{x}}$ and $\overline{\mathbf{y}}$ be unit $\ell_{2}$-norm vectors satisfying the desired constraints. If you expand the objective function you should see that the objective is to maximize the inner products $\mathbf{x}^{\top}\mathbf{u}_{1}$ and $\mathbf{y}^{\top}\mathbf{v}_{1}$, which can be easily done. Then you need to scale the product $\mathbf{x}\mathbf{y}^{\top}$ appropriately, but the scaling factor can again be easily determined.

• Under this assumption, even the problem of approximating $\mathbf{A}$ with $\mathbf{B}^{\prime}$ is easy: just have to focus on the upper right $n_{1} \times m_{1}$ block of $\mathbf{B}$ and compute its singular vectors. Padding those with zeros, will give you the desired $\mathbf{x}$ and $\mathbf{y}$.

2. The problem of approximating a general matrix $\mathbf{A}$ with a matrix $\mathbf{B}^{\prime}$ satisfying those restrictions is generally NP-hard: for $n_{1}=0$ and $m_{1}=0$, and very large $\epsilon$, the problem is equivalent to seeking the best nonnegative rank-1 approximation of $\mathbf{A}$, which is an NP-hard problem, unless $\mathbf{A}$ is a nonnegative matrix. What this means is that if $\mathbf{A}$ is nonnegative, then it is easy to compute the top pair of nonnegative singular vectors (and hence the reduction does not work) --it does not mean that your restricted problem is easy.

• @megas...thanks for the reply. I got first part of your answer for $\epsilon=0$. But I am not clear about the later half. $\mathbf{B}$ is a rank-1 matrix. Also making $n_1=m_1=0$ would mean that all elements of $\mathbf{x}$ & $\mathbf{y}$ are $\in (0,\epsilon)$. Can you please elaborate this. – NAASI Sep 27 '16 at 15:57
• Secondly if $\mathbf{A}$ is a non-negative matrix then your answer suggests that finding $\mathbf{B'}$ is possible. Is this correct? – NAASI Sep 27 '16 at 15:58
• @NAASI I am sorry for the confusion; I thought that your $\mathbf{B}^{\prime}$ would be computed from the original matrix $\mathbf{A}$. For the second part, I meant that the problem of computing nonnegative components (without the "sparsity" constraint) is easy when $\mathbf{A}$ is nonnegative, but hard in general. I will edit the answer to clarify a few things. – megas Sep 27 '16 at 16:53
• I appreciate your reply. Can you edit your answer with emphasis on non-negative matrix $\mathbf{A}$. I just posted this new question here math.stackexchange.com/questions/1943785/… – NAASI Sep 27 '16 at 16:59