3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ You are correct, I expanded a bit. Sorry about being impolite. $\endgroup$
    – Paul Irofti
    Commented May 29, 2017 at 8:33
  • $\begingroup$ 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. $\endgroup$
    – Federico Poloni
    Commented May 29, 2017 at 9:20
  • $\begingroup$ search for "column subset selection" and you'll find numerous papers that provide approximation algorithms for solving such problems. $\endgroup$
    – Suvrit
    Commented Jul 28, 2017 at 12:31

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Paul Irofti
    Commented May 29, 2017 at 8:42
  • $\begingroup$ 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. $\endgroup$
    – Paul Irofti
    Commented May 29, 2017 at 8:42
  • 1
    $\begingroup$ 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? $\endgroup$
    – Rodrigo de Azevedo
    Commented May 29, 2017 at 8:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – Federico Poloni
    Commented May 29, 2017 at 9:18
  • $\begingroup$ ($A-A_I$ in the LHS, not $A-I$, sorry.) $\endgroup$
    – Federico Poloni
    Commented May 29, 2017 at 12:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .