<p>This is the median k-flat problem. Feldman wrote some papers on this and related problems. See for example  <a href="http://arxiv.org/abs/1106.1379" rel="nofollow">http://arxiv.org/abs/1106.1379</a> .</p>

CC BY-SA 3.0
2016-01-17T22:09:19.920Z
2016-01-17T22:09:19.920Z
Sariel Har-Peled
<p>Theorem 14 of <a href="http:///http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/lehre/AlgorithmsForBigData/sarlos_06_matrix-approximation.pdf" rel="nofollow">this</a> paper by Tam´as Sarl´os gives a relative error rank-$k$ approximation of a given matrix $A$ under the <a href="https://en.wikipedia.org/wiki/Matrix_norm#Frobenius_norm" rel="nofollow">frobenius</a> norm. I am looking for reference of a similar result (relative error low rank approximation) under the $l_2$ norm.</p>

<p>Pls let me know I am  able to put the question clearly.</p>

CC BY-SA 3.0
2016-01-11T09:42:56.593Z
@RickyDemer Yes.
Ram
<linear-algebra><matrices>
Low rank approximation of matrix under $l_2$ norm
Ram
# Low rank approximation of matrix under $l_2$ norm

(Asked by: username_0 on 2016-01-11)

Theorem 14 of [this](http:///http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/lehre/AlgorithmsForBigData/sarlos_06_matrix-approximation.pdf) paper by Tam´as Sarl´os gives a relative error rank-$k$ approximation of a given matrix $A$ under the [frobenius](https://en.wikipedia.org/wiki/Matrix_norm#Frobenius_norm) 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.

**Tags:** linear-algebra, matrices

> **Comments:**
> **username_0**: @RickyDemer Yes.  

---

## 1 answers

### Answer by username_1 on 2016-01-17. Score: 2 | Accepted answer

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> .


---

