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
    Commented Jan 11, 2016 at 9:37
  • $\begingroup$ @RickyDemer Yes. $\endgroup$
    – Ram
    Commented Jan 11, 2016 at 9:42

1 Answer 1


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 and acknowledge you have read our privacy policy.

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