0
$\begingroup$

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}$

\begin{equation} \mathbf{B}=\sigma_1*\mathbf{u}_1*\mathbf{v}_1^{T} \end{equation}

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<x_i<\epsilon \hspace{2mm}\forall i=n_1+1,\dots,n$
  2. $\mathbf{y}\in\mathbb{R}^{m\times 1}$ and last $(m-m_1)$ elements of $\mathbf{y}$ are $0<y_j<\epsilon \hspace{2mm}\forall j=m_1+1,\dots,m$

$${\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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – megas Sep 27 '16 at 0:17
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – NAASI Sep 27 '16 at 15:57
  • $\begingroup$ Secondly if $\mathbf{A}$ is a non-negative matrix then your answer suggests that finding $\mathbf{B'}$ is possible. Is this correct? $\endgroup$ – NAASI Sep 27 '16 at 15:58
  • $\begingroup$ @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. $\endgroup$ – megas Sep 27 '16 at 16:53
  • $\begingroup$ 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/… $\endgroup$ – NAASI Sep 27 '16 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.