suresh at cs utah edu
Ph: 801 581 8233
Room 3404, School of Computing
50 S. Central Campus Drive,
Salt Lake City, UT 84112.
Moving heaven and earth: distances between distributions [author]Suresh Venkatasubramanian[/author] SIGACT News vol 44, no. 3.

New Developments in Matrix Factorization.

SIGACT News 44 (1), March 2013.

Notes: the published version of the article has a few errors.

  • Moitra’s SODA paper improves the running time from $O((nm)^{2^r r^2})$ to $O((nm)^{r^2})$, which is considerably stronger than what was reported in the article.
  • The correct lower bound for computing a nonnegative factorization (assuming ETH) is $O((nm)^{o(r)})$.

This link (PDF) has the corrected article. Thanks to Ankur Moitra for pointing out the errors.