Say a reconstruction of matrix $A$ is $A'$ and it's defined as
$$
A' = PDP^TA
$$
where $P$ is an orthogonal 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. $\operatorname{Tr}(D)=n$ that would minimize $\lVert A-A'\rVert$? $P$ and $A$ are fixed.


I think I need to inspect the singular vectors of $A$, but I am not sure what to do exactly. I think the 1's in $D$ should indicate columns of $P$ that best align with the column space of $A$, but what how do I determine the "best" alignment?



Matrix reconstruction puzzle
[EDIT: as OP confirm that they need the Frobenius norm, this should be a complete solution for that case]


Since that norm is orthogonally invariant,
$$
\|A - A'\| = \|P^T(A-A')\| = \|P^TA - DP^TA\| = \|(I-D)P^TA\|,
$$
so essentially the question becomes "you are allowed to zero out $n$ rows of $B= P^TA$; which choice leaves you with the minimum norm"? This looks like a simpler reformulation.


If the norm is the Frobenius norm, then the answer is choosing the $n$ rows with the largest norm; I suspect that the same holds also for the 2-norm, but this is not immediate and sometimes these kinds of problems have a different solution when one switches norm.


