Sparse matrix approximation using only a few dense columns (or rows) Given a dense matrix $A \in \mathbb{R}^{n \times m}$, with $n < m$, I am interested in finding a good approximation by choosing $s$ rows and zeroing the rest. This leads me to the following optimization problem
$$\underset{A_I}{\min}\left\lVert A - A_I \right\rVert_F^2$$
where $I$ is the index set of $s$ selected rows and $A_I$ is the restriction to this set (with rows $I^c$ set to zero). Are there any known results in this direction? 
Smola's paper seems to be close to what I want, but I can not follow its notation when performing column selection. Is $K_i$ a matrix or a column in Equation (11)? At first I thought it was about columns, but then when discussing selection strategies in Equation (25) it seems that there is a Gram-Schmidt-like linear relationship between $K_i$'s even though the previous selected columns are already orthogonal.
 A: Since this is getting bumped to the home page, I'll turn my comment into an answer.
We have
$$\|A-A_I\|^2_F = \sum_{i \not \in I} \|a_i\|^2,$$
where $a_i$ are the rows of $A$, so it is clear that the solution is taking in $I$ the $s$ rows with the largest norms.
A: Selecting $s \leq n$ rows can be done by left-multiplying $\rm A$ by a Boolean diagonal matrix with $s$ ones on its main diagonal. Hence, we have the following Boolean optimization problem
$$\begin{array}{ll} \text{minimize} & \| \mathrm A - \mbox{diag} (\mathrm x) \mathrm A \|_{\text{F}}^2\\ \text{subject to} & 1_n^{\top} \mathrm x = s\\ & \mathrm x \in \{0,1\}^n\end{array}$$
Note that
$$\mathrm A - \mbox{diag} (\mathrm x) \mathrm A = \left( \mathrm I_n - \mbox{diag} (\mathrm x) \right) \mathrm A = \left( \mbox{diag} (\mathrm 1_n) - \mbox{diag} (\mathrm x) \right) \mathrm A = \mbox{diag} (\underbrace{\mathrm 1_n - \mathrm x}_{=: \mathrm y}) \mathrm A = \mbox{diag} (\mathrm y) \mathrm A$$
Hence,
$$\begin{array}{ll} \text{minimize} & \| \mbox{diag} (\mathrm y) \mathrm A \|_{\text{F}}^2\\ \text{subject to} & 1_n^{\top} \mathrm y = n - s\\ & \mathrm y \in \{0,1\}^n\end{array}$$
where
$$\| \mbox{diag} (\mathrm y) \mathrm A \|_{\text{F}}^2 = \mbox{tr} ( \mathrm A^{\top} \mbox{diag}^2 (\mathrm y) \,\mathrm A) = \mbox{tr} ( \mathrm A^{\top} \mbox{diag} (\mathrm y) \,\mathrm A) = \mbox{tr} ( \mathrm A \mathrm A^{\top} \mbox{diag} (\mathrm y) ) = \langle \mathrm A \mathrm A^{\top}, \mbox{diag} (\mathrm y) \rangle$$
Let $\mathrm c \geq 0_n$ be the (nonnegative) vector whose $n$ entries are the entries on the main diagonal of the $n \times n$ Gram matrix $\mathrm A \mathrm A^{\top}$. Thus, we have the following binary integer program (IP) in $\mathrm y \in \mathbb Z^n$
$$\begin{array}{ll} \text{minimize} & \mathrm c^{\top} \mathrm y\\ \text{subject to} & 1_n^{\top} \mathrm y = n - s\\ & 0_n \leq \mathrm y \leq 1_n\\ & \mathrm y \in \mathbb Z^n\end{array}$$
We conclude that we select the $s$ rows of $\rm A$ with the $s$ largest $2$-norms. The minimum is the sum of the $2$-norms of the $n-s$ rows of $\rm A$ with the $n-s$ smallest $2$-norms.
