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.

• You are correct, I expanded a bit. Sorry about being impolite. – Paul Irofti May 29 '17 at 8:33
• It seems from your comments that some constraints are missing from the problem description. Please review it and make sure you are not missing anything. – Federico Poloni May 29 '17 at 9:20
• search for "column subset selection" and you'll find numerous papers that provide approximation algorithms for solving such problems. – Suvrit Jul 28 '17 at 12:31

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.

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.

• I reached the same result initially, but I think that using an iterative algorithm that attempts to maximize the residual minimization at each step makes more sense in this scenario then picking the largest $s$ rows. My reasoning is as follows, say we select 2 largest 2-norm rows. Each row on its own will surely have a large impact on reducing the residual. But once I select the largest row, the second largest might not continue to be the most important row because the two rows might be pointing in the same direction. – Paul Irofti May 29 '17 at 8:42
• Whereas an iterative algorithm would pick the largest 2-norm row, and then pick the 2nd row whose orthogonal projection on the current residual is largest. And so on, and so forth. This is the OMP approach for matrices instead of vectors, which is what I expected out of Smola's paper that I cited in my question. – Paul Irofti May 29 '17 at 8:42
• If the goal is to minimize the squared Frobenius norm, why worry if two rows are linearly dependent? There are no constraints on the rank, are there? – Rodrigo de Azevedo May 29 '17 at 8:46
• Isn't this answer killing flies with cannons? $\|A-I\|^2_F = \sum_{i \not \in I} \|a_i\|^2$, where $a_i$ are the rows of $A$, so it seems clear that the solution is taking the rows with maximum norms. – Federico Poloni May 29 '17 at 9:18
• ($A-A_I$ in the LHS, not $A-I$, sorry.) – Federico Poloni May 29 '17 at 12:00