Subset of $h$ rows of $A$ with minimal norm

Question

I have a matrix $A \in \mathbb{R}^{n \times p}$ and a fixed $h \in \mathbb{N}$. I want to find a subset of $h$ rows so that the $\| \cdot \|_2$ norm of the resulting sub-sample of $A$ is minimal.

I would assume that obtaining the global minimum is not feasible, but are there algorithms to approximate it?

Answer 1

Since $\|B\|_2 \leq \sqrt h \|B\|_{\infty}$, for every $h\times n$ matrix $B$, one can find $\sqrt h$ approximate algorithm by finding $h$ rows of $A$ with smallest 1-norm.