¿Por qué la minimización de la norma nuclear de una matriz es un buen sustituto de la minimización del rango?

Question

Un método llamado "Robust PCA" resuelve el problema de descomposición de la matriz

$$L^*, S^* = \arg \min_{L, S} \|L\|_* + \|S\|_1 \quad \text{s.t. } L + S = X$$

como un sustituto del problema real

$$L^*, S^* = \arg \min_{L, S} rank(L) + \|S\|_0 \quad \text{s.t. } L + S = X,$$ es decir, el objetivo real es descomponer la matriz de datos $X$ en una matriz de señal de bajo rango $L$ y una matriz de ruido dispersa $S$ . En este contexto: ¿por qué la norma nuclear es una buena aproximación al rango de una matriz? Se me ocurren matrices con baja norma nuclear pero con alto rango y viceversa. ¿Hay alguna intuición a la que se pueda apelar?

Answer 1

¿Por qué detección comprimida ¿trabajo? Porque el $\ell_1$ La bola de altas dimensiones es extremadamente "puntiaguda": es muy probable que los valores extremos de una función lineal en esta bola se alcancen en las caras de bajas dimensiones, las que están formadas por vectores dispersos. Cuando se aplica a las matrices, la escasez del conjunto de valores propios significa un rango bajo, como escribió @mrig antes que yo.

Answer 2

Para ser exactos, se ha demostrado que el $\ell_1$ es la norma sobre convexo de la $\| \cdot \|_0$ pseudo-norma mientras que la norma nuclear es la sobre convexo del rango.

Como recordatorio, la envolvente convexa es el sustituto convexo más ajustado de una función. Una propiedad importante es que una función y su envolvente convexa tienen la misma minimizador global .

Answer 3

La norma nuclear puede considerarse como una relajación convexa del número de valores propios distintos de cero (es decir, el rango).

Answer 4

La norma nuclear de una matriz es equivalente a la norma L1 del vector de sus valores propios. Por lo tanto, se está inyectando la sparsity al vector de valores propios. Básicamente, esta dispersión significa que se está reduciendo el rango de la matriz original.

Answer 5

Gracias por hacer esta pregunta. Tengo problemas para entender lo mismo. En particular, lo siguiente.

Aunque la norma nuclear es una relajación para el rango, no entiendo cómo la norma nuclear puede funcionar como sustituto para minimizar el rango a menos que sea un límite superior para el rango.

Como se señaló en el post original, la norma nuclear no parece proporcionar un límite (inferior o superior) al rango de la matriz. Por ejemplo, considere lo siguiente.

1)
A: #<BASIC-MATRIX (2 2)      2.00000      0.00000 \\
                             0.00000      2.00000 >
 (RANK A): 2
 (NUCLEAR-NORM A): 4.0d0

2)
 A: #<BASIC-MATRIX (2 2)      0.10000      0.00000 \\
                              0.00000      0.10000 >
 (RANK A): 2
 (NUCLEAR-NORM A): 0.20000000298023224d0

En 1) la norma nuclear es mayor que el rango mientras que en 2) es menor que el rango.