1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ @FedericoPoloni Yes $\endgroup$
    – CWC
    Commented Apr 10, 2021 at 11:59

1 Answer 1

Reset to default
3
$\begingroup$

[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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I see. I meant Frobenius norm. So I need to permute the rows/columns of $D$ until I can maximize $||DB||$. Since the extreme points of Birkhoff polytope (polytope of doubly stochastic matrices) are permutation matrices, I can do linear programming to find the solution. Thanks! $\endgroup$
    – CWC
    Commented Apr 10, 2021 at 12:22
  • $\begingroup$ Stupid question: it intuitively makes sense to find maximum solution, but how does minimizing $||DP^TA-P^TA||$ becomes maximizing $||DP^TA||$? $\endgroup$
    – CWC
    Commented Apr 10, 2021 at 12:24
  • $\begingroup$ @ChanwooChun Sorry, I had switched $D$ and $I-D$ in my head at some point; now it should be fixed (and clearer). Anyhow, you do not need to do any linear programming; just compute the norm of each row of $B$, find the largest $n$ norms, and put ones in the corresponding rows of $D$. $\endgroup$
    – Federico Poloni
    Commented Apr 10, 2021 at 12:43
  • $\begingroup$ That makes perfect sense. I think there are still some typos though. Thanks again! $\endgroup$
    – CWC
    Commented Apr 10, 2021 at 13:24
  • $\begingroup$ Rechecked, thanks. Feel free to edit the answer if you spot more typos. $\endgroup$
    – Federico Poloni
    Commented Apr 10, 2021 at 13:26

You must log in to answer this question.

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