Say a reconstruction of matrix $A$ is $A'$ and it's defined as
$ A' = P^TDPA $
where $P$ is an orthonormal matrix, $D$ is a diagonal binary (1 or 0) matrix. In a trivial case, when all diagonal elements are 1, we have a perfect reconstruction ($A'=A$).
Now we constrain the number of 1's in the diagonal entries of $D$ to, say, $n$. How do I find the best $D$ s.t. $Tr(D)=n$ that would minimize $||A-A'||$?
I think I need to inspect the singular vectors of $A$, but I am not sure what to do exactly.
$D = argmin_{D\in\text{binary diag}}\quad ||P^\top DPA - A||$ Now let's change basis for A using $P$ (which is orthonormal). Thus $\exists M$ such $A = P^\top MP$. Note that M is deterministic as we know $P$ and $A$.
Making this substitution in the first equation, we get \begin{align*} D &= argmin_{D\in\text{binary diag}}\quad ||P^\top DPP^\top MP - P^\top MP||\\ &= argmin_{D\in\text{binary diag}}\quad ||P^\top D MP - P^\top MP||\\ &= argmin_{D\in\text{binary diag}}\quad ||P^\top (D M-M) P||\\ \end{align*} Now comes the crucial part, since P is orthonormal (equivalent to original basis), this optimization problem is the same as: \begin{align*} D &= argmin_{D\in\text{binary diag}}\quad ||D M-M||\\ &= argmin_{D\in\text{binary diag}}\quad ||(D-I) M||\\ \end{align*}
Thus, we choose D such that the 1's correspond to the maximum norm rows of $M$