Incomplete low-rank matrices can be exactly recovered in most cases, so long as the rank is low enough relative to the number of known entries. This result was famously proved by Candès and Recht in the paper "Exact Matrix Completion via Convex Optimization". Algorithmically, the nuclear norm minimization that recovers the full matrix requires keeping the entire data matrix in memory, and only after convergence can the matrix be reduced to its low-rank parts.

Suppose we know that our matrix $X\in\mathbb{R}^{n\times n}$ is rank one: $X = uv^T$, $u$, $v\in\mathbb{R}^n$. When $n$ is large, keeping $X$ in memory may be intractable, even if it's very tractable to keep $u$ and $v$. A nice identity about the nuclear norm is that $||X||_* = \min_{u,v\,st\,uv^T=X} \frac{1}{2}||u||^2_2 + \frac{1}{2}||v||^2_2$, so it is possible to recast nuclear norm minimization as a minimization over $u$ and $v$ constrained such that $uv^T$ agrees with known entries of $X$. My question is this: can we carry out this minimization tractably? Will we still converge to the exact solution? How do we perform this minimization?


migrated from stats.stackexchange.com Feb 6 '14 at 16:26

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

  • $\begingroup$ It seems to me that the ratio of any two non-zero columns of $X$ will give you $u$ and the ratio of any two non-zero rows will give you $v^\prime$ without any further effort. $\endgroup$ – whuber Feb 6 '14 at 16:29
  • $\begingroup$ Except there's an arbitrary scale factor between $u$ and $v$, and the rows and columns of $X$ will have lots of missing entries. $\endgroup$ – David Pfau Feb 6 '14 at 17:10
  • $\begingroup$ Thanks--I didn't catch the "incomplete" part (even though it's your very first word!). $\endgroup$ – whuber Feb 6 '14 at 17:21

I realized that specifically in the rank one case, this can be turned into a convex program by a change of variables. Let $\{i_1,\ldots,i_K\}$ and $\{j_1,\ldots,j_K\}$ be the row and column indices of the observed entries in $X$, our problem is to minimize $\frac{1}{2}||u||_2^2 + \frac{1}{2}||v||_2^2$ under the constraint $u_{i_k}v_{j_k} = X_{i_k j_k}\forall k = 1,\ldots,K$. Then let $p_i = \mathrm{log}(u_i)$ and let $q_j = \mathrm{log}(v_j)$, the transformed problem becomes:

$\min_{p,q} \frac{1}{2}\sum_i \mathrm{exp}(p_i)\overline{\mathrm{exp}(p_i)} + \frac{1}{2}\sum_i \mathrm{exp}(q_j)\overline{\mathrm{exp}(q_j)}$

with linear equality constraints $p_{i_k} + q_{j_k} = \mathrm{log}(X_{i_k j_k})$, which is a convex problem over complex numbers (or over real numbers if $X$ is nonnegative). Of course this doesn't extend to anything above rank one, as the constraints on $u$ and $v$ go from being products to sums of products. However, it does extend to arbitrary rank one tensors!

For anyone interested in going beyond the rank one case, here are some resources (courtesy of Rahul Mazumder):

Spectral Regularization Algorithms for Learning Large Incomplete Matrices: Describes an algorithm for matrix completion that allows you to work with the reduced singular value decomposition of $X$ instead of the entirety of $X$.

There are also some results suggesting that, when working with $U$ and $V$ rather than $X$, even if the convergence is to a local minimum in $U$ and $V$, this corresponds to the global minimum in $X$, for instance: Local minima and convergence in low-rank semidefinite programming.


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.