Qual norma do erro de reconstrução é minimizada pela matriz de aproximação de baixa classificação obtida com o PCA?

Resposta em uma única palavra: Ambos.

Vamos começar definindo as normas. Para uma matriz , o operador -norm é definido como $X$ $2$ e norma Frobenius como

‖ X ‖_{2} = s u p \frac{‖ X v ‖_{2}}{‖ v ‖_{2}} = m a x (s_{i})

$\|X\|_2 = \mathrm{sup}\frac{\|Xv\|_2}{\|v\|_2} = \mathrm{max}(s_i)$

onde

são valores singulares de

, ou seja, os elementos da diagonal de

na decomposição de valor singular

‖ X ‖_{F} = \sqrt{\sum_{i j} X_{i j}^{2}} = t r (X^{⊤} X) = \sqrt{\sum s_{i}^{2}},

$\|X\|_F = \sqrt {\sum_{ij} X_{ij}^2} = \mathrm{tr}(X^\top X) = \sqrt{\sum s_i^2},$

s_{i}

$s_i$

X

$X$

S

$S$

X = U S V^{⊤}

$X = USV^\top$

O PCA é fornecido pela mesma decomposição de valor singular quando os dados são centralizados. são componentes principais, são eixos principais, ou seja, autovetores da matriz de covariância, e a reconstrução de com apenas os componentes principais correspondentes aos maiores valores singulares é dada por . $US$ $V$ $X$ $k$ $k$ $X_k = U_k S_k V_k^\top$

O teorema de Eckart-Young diz que é a matriz que minimiza a norma do erro de reconstrução entre todas as matrizes da classificação . Isso é verdade tanto para a norma Frobenius quanto para o operador $X_k$ $\|X-A\|$ $A$ $k$ $2$ -norm. Como apontado por @cardinal nos comentários, foi provado por Schmidt (da fama de Gram-Schmidt) em 1907 para o caso Frobenius. Mais tarde foi redescoberto por Eckart e Young em 1936 e agora está associado principalmente a seus nomes. Mirsky generalizou o teorema em 1958 a todas as normas que são invariantes sob transformações unitárias, e isso inclui o operador 2-norma.

Esse teorema às vezes é chamado de teorema de Eckart-Young-Mirsky. Stewart (1993) o chama de teorema da aproximação de Schmidt. Eu já o vi chamado teorema de Schmidt-Eckart-Young-Mirsky.

Eckart e Young, 1936, A aproximação de uma matriz por outra de nível mais baixo
Mirsky, 1958, Funções de medidor simétrico e normas invariavelmente invariáveis
Stewart, 1993, Sobre a história inicial da decomposição de valores singulares

Prova para o operador -norm $2$

Seja de posição completa . Como é da classificação , seu espaço nulo tem dimensões. O espaço medido pelos vetores singulares à direita de correspondentes aos maiores valores singulares possui dimensões. Portanto, esses dois espaços devem se cruzar. Seja um vetor unitário da interseção. Em seguida, obtemos: $X$ $n$ $A$ $k$ $n-k$ $k+1$ $X$ $k+1$ $w$ QED.

‖ X - A ‖_{2}^{2} \geq ‖ (X - A) w ‖_{2}^{2} = ‖ X w ‖_{2}^{2} = \sum_{i = 1}^{k + 1} s_{i}^{2} (v_{i}^{⊤} w)^{2} \geq s_{k + 1}^{2} = ‖ X - X_{k} ‖_{2}^{2},

$\|X-A\|^2_2 \ge \|(X-A)w\|^2_2 = \|Xw\|^2_2 = \sum_{i=1}^{k+1}s_i^2(v_i^\top w)^2 \ge s_{k+1}^2 = \|X-X_k\|_2^2,$

Prova da norma Frobenius

Queremos encontrar matriz de classificação que minimiza . Podemos fatorar , onde tem colunas ortonormais. Minimizando para fixa é um problema de regressão com solução . Ligá-lo, vemos que precisamos agora para minimizar $A$ $k$ $\|X-A\|^2_F$ $A=BW^\top$ $W$ $k$ $\|X-BW^\top\|^2$ $W$ $B=XW$ onde é a matriz de covariância de , ou seja, . Isso significa que o erro de reconstrução é minimizado tomando como colunas de alguns

‖ X - X W W^{⊤} ‖^{2} = ‖ X ‖^{2} - ‖ X W W^{⊤} ‖^{2} = c o n s t - t r (W W^{⊤} X^{⊤} X W W^{⊤}) = c o n s t - c o n s t \cdot t r (W^{⊤} Σ W),

$\|X-XWW^\top\|^2=\|X\|^2-\|XWW^\top\|^2=\mathrm{const}-\mathrm{tr}(WW^\top X^\top XWW^\top)\\=\mathrm{const}-\mathrm{const}\cdot\mathrm{tr}(W^\top\Sigma W),$

Σ

$\Sigma$

X

$X$

Σ = X^{⊤} X / (n - 1)

$\Sigma=X^\top X/(n-1)$

W

$W$

k

$k$ ortonormal vectores maximizar a variância total da projecção.

É sabido que estes são os primeiros vetores da matriz de covariância. De fato, se , então . Escrita que também tem colunas ortonormais, obtemos $k$ $X=USV^\top$ $\Sigma=VS^2V^\top/(n-1)=V\Lambda V^\top$ $R=V^\top W$

t r (W^{⊤} Σ W) = t r (R^{⊤} Λ R) = \sum_{i} λ_{i} \sum_{j} R_{i j}^{2} \leq \sum_{i = 1}^{k} λ_{k},

$\mathrm{tr}(W^\top\Sigma W)=\mathrm{tr}(R^\top\Lambda R)=\sum_i \lambda_i \sum_j R_{ij}^2 \le \sum_{i=1}^k \lambda_k,$

W = V_{k}

$W=V_k$ . O teorema segue imediatamente.

Consulte os três segmentos relacionados a seguir:

Tentativa anterior de uma prova da norma Frobenius

Esta prova eu encontrei em algum lugar online, mas está errado (contém uma lacuna), conforme explicado por @cardinal nos comentários.

‖ X - A ‖_{F} = ‖ U S V^{⊤} - A ‖ = ‖ S - U^{⊤} A V ‖ = ‖ S - B ‖,

$\|X-A\|_F=\|USV^\top - A\| = \|S - U^\top A V\| = \|S-B\|,$

B = U^{⊤} A V

$B=U^\top A V$

‖ X - A ‖_{F} = \sum_{i j} (S_{i j} - B_{i j})^{2} = \sum_{i} (s_{i} - B_{i i})^{2} + \sum_{i \neq j} B_{i j}^{2} .

$\|X-A\|_F = \sum_{ij}(S_{ij}-B_{ij})^2 = \sum_i (s_i-B_{ii})^2 + \sum_{i\ne j}B_{ij}^2.$ This is minimized when all off-diagonal elements of

B

$B$ are zero and all

k

$k$ diagonal terms cancel out the

k

$k$ largest singular values

s_{i}

$s_i$ [gap here: this is not obvious], i.e.

B_{o p t i m a l} = S_{k}

$B_\mathrm{optimal}=S_k$ and hence

A_{o p t i m a l} = U_{k} S_{k} V_{k}^{⊤}

$A_\mathrm{optimal} = U_k S_k V_k^\top$ .

amoeba says Reinstate Monica
fonte

The proof in the case of the Frobeniius norm is not correct (or at least complete) since the argument here does not preclude the possibility that a matrix of the same rank could cancel out some of the other diagonal terms while having "small" off-diagonals. To see the gap more clearly note that holding the diagonals constant and "zeroing" the off-diagonals can often increase the rank of the matrix in question!

cardinal

Note also that the SVD was known to Beltrami (at least in a quite general, though special case) and Jordan as early as 1874.

cardinal

@cardinal: Hmmmm, I am not sure I see the gap. If

B

$B$ cancels out some other diagonal terms in

S

$S$ instead of

k

$k$ largest ones and has some nonzero off-diagonal terms instead, then both sums,

\sum_{i} (s_{i} - B_{i i})^{2}

$\sum_{i}(s_i-B_{ii})^2$ and

\sum_{i \neq j} B_{i j}^{2}

$\sum_{i\ne j}B_{ij}^2$ , are going to increase. So it will only increase the reconstruction error. No? Still, I tried to find another proof for Frobenius norm in the literature, and have read that it should somehow follow easily from the operator norm case. But so far I don't see how it should follow...

amoeba says Reinstate Monica

I do like G. W. Stewart (1993), On the early history of the singular value decomposition, SIAM Review, vol. 35, no. 4, 551-566 and, given your prior demonstrated interest in historical matters, I think you will too. Unfortunately, I think Stewart is unintentionally overly dismissive of the elegance of Schmidt's 1907 proof. Hidden within it is a regression interpretation that Stewart overlooks and which is really quite pretty. There is another proof that follows the initial diagonalization approach you take, but which requires some extra work to fill the gap. (cont.)

cardinal

@cardinal: Yes, you are right, now I see the gap too. Thanks a lot for the Stewart paper, that was a very interesting read. I see that Stewart presents Schmidt's and Weyl's proofs, but both of them look more complicated than what I would like to copy here (and so far I have not had the time to study them carefully). I am surprised: I expected this to be a very simple result, but it seems it is less trivial than I thought. In particular, I would not have expected that the Frobenius case is so much more complicated than the operator norm one. I will edit the post now. Happy New Year!

amoeba says Reinstate Monica

Qual norma do erro de reconstrução é minimizada pela matriz de aproximação de baixa classificação obtida com o PCA?

Respostas:

Resposta em uma única palavra: Ambos.

Prova para o operador -norm222

Prova da norma Frobenius

Tentativa anterior de uma prova da norma Frobenius

Prova para o operador -norm $2$