http://www.cs.utah.edu/~suresh
suresh at cs utah edu
Ph: 801 581 8233
Room 3404, School of Computing
50 S. Central Campus Drive,
Salt Lake City, UT 84112.
New Developments in Matrix Factorization.
Wednesday March 13th 2013, 9:33 pm
Filed under: Papers

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.

Tags:



2 Comments so far

Suresh,

You might be interested in this work:
http://nuit-blanche.blogspot.com/2013/02/robust-near-separable-nonnegative.html

Igor.

Comment by Igor Carron 03.20.13 @ 2:00 pm

Minor typo? — In Section 1.1, paragraph 2: “It says that the operation of applying A can be viewed…” ; should be “…of applying M” ?

Comment by Roddy Collins 03.29.13 @ 8:58 am



Leave a comment
Line and paragraph breaks automatic, e-mail address never displayed, HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

(required)

(required)