Rompecabezas de la reconstrucción de la matriz

Question

Digamos que una reconstrucción de la matriz $A$ es $A'$ y se define como

$ A' = P^TDPA $

donde $P$ es una matriz ortonormal, $D$ es una matriz diagonal binaria (1 o 0). En un caso trivial, cuando todos los elementos diagonales son 1, tenemos una reconstrucción perfecta ( $A'=A$ ).

Ahora restringimos el número de 1's en las entradas diagonales de $D$ a, digamos, $n$ . ¿Cómo puedo encontrar el mejor $D$ s.t. $Tr(D)=n$ que minimizaría $||A-A'||$ ?

Creo que necesito inspeccionar los vectores singulares de $A$ Pero no sé qué hacer exactamente.

Answer 1

$D = argmin_{D\in\text{binary diag}}\quad ||P^\top DPA - A||$ Ahora vamos a cambiar la base de A utilizando $P$ (que es ortonormal). Así, $\exists M$ tal $A = P^\top MP$ . Obsérvese que M es determinista como sabemos $P$ y $A$ .

Haciendo esta sustitución en la primera ecuación, obtenemos \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*} Ahora viene la parte crucial, ya que P es ortonormal (equivalente a la base original), este problema de optimización es el mismo que: \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*}

Por lo tanto, elegimos D de manera que los 1's correspondan a las filas de norma máxima de $M$