Theorem 14 of this paper by Tam´as Sarl´os gives a relative error rank-$k$ approximation of a given matrix $A$ under the frobenius norm. I am looking for reference of a similar result (relative error low rank approximation) under the $l_2$ norm.

Pls let me know I am able to put the question clearly.

  • $\begingroup$ "$l_2$ norm" ​ = ​ "Euclidean operator norm" ​ ​ ​ ? ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user6973 Jan 11 '16 at 9:37
  • $\begingroup$ @RickyDemer Yes. $\endgroup$ – Ram Jan 11 '16 at 9:42

This is the median k-flat problem. Feldman wrote some papers on this and related problems. See for example http://arxiv.org/abs/1106.1379 .


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.