CUR-matrisuppskattning

En CUR-matrisapproximation är en uppsättning av tre matriser som, när de multipliceras tillsammans, nära approximerar en given matris. En CUR-approximation kan användas på samma sätt som den låggradiga approximationen av singular value decomposition ( SVD). CUR-uppskattningar är mindre exakta än SVD, men de erbjuder två viktiga fördelar, båda härrör från det faktum att raderna och kolumnerna kommer från den ursprungliga matrisen (istället för vänster och höger singularvektorer):

• Det finns metoder för att beräkna det med lägre asymptotisk tidskomplexitet jämfört med SVD.
• Matriserna är mer tolkbara; Betydelsen av rader och kolumner i den sönderdelade matrisen är i huvudsak desamma som deras betydelser i den ursprungliga matrisen.

Formellt är en CUR-matrisapproximation av en matris A tre matriser C , U och R så att C är gjord av kolumner av A , R är gjord från rader av A , och att produkten CUR nära approximerar A . Vanligtvis väljs CUR för att vara en rank - k approximation, vilket betyder att C innehåller k kolumner av A , R innehåller k rader av A och U är en k -by- k matris. Det finns många möjliga CUR-matrisapproximationer och många CUR-matrisapproximationer för en given rang.

CUR-matrisapproximationen används ofta i stället för lågrankad approximation av SVD i principal komponentanalys . CUR är mindre exakt, men kolumnerna i matrisen C är hämtade från A och raderna i R är hämtade från A . I PCA innehåller varje kolumn i A ett dataprov; sålunda är matrisen C gjord av en delmängd av datasampel. Detta är mycket lättare att tolka än SVD:s vänstra singularvektorer, som representerar data i ett roterat utrymme. På liknande sätt är matrisen R gjord av en delmängd av variabler som mäts för varje dataprov. Detta är lättare att förstå än SVD:s högra singularvektorer, som är ytterligare en rotation av data i rymden.

Matematisk definition

Hamm och Huang ger följande teorem som beskriver grunderna för en CUR-nedbrytning av en matris $L$ med rang $r$ :

Sats: Betrakta rad- och kolumnindex $I,J\subseteq [n]$ med $|I|,|J|\geq r$ . Beteckna submatriserna $C=L_{:,J},$$U=L_{I,J}$ och $R=L_{I,:}$ . Om rank( $U$ ) = rank( $L$ ), då $L=CU^{+}R$ , där $( \cdot )^{+}$ betecknar Moore–Penrose-pseudoinversen .

Med andra ord, om $L$ har låg rang, kan vi ta en delmatris $U=L_{I,J}$ av samma rang, tillsammans med några rader $R$ och kolumner $C$ i $L$ och använd dem för att rekonstruera $L$ .

Algoritmer

CUR-matrisuppskattningen är inte unik och det finns flera algoritmer för att beräkna en. En är ALGORITHMCUR.

Algoritmen "Linjär tid CUR" väljer helt enkelt J genom att sampla kolumner slumpmässigt (med ersättning) med sannolikhet proportionell mot de kvadratiska kolumnnormerna, $\|L_{:,j}\|_{ 2}^{2}$ ; och på liknande sätt sampling I proportionell mot de kvadratiska radnormerna, $\|L_{i}\|_{2}^{2}$ . Författarna visar att ta $|J|\approx k/\varepsilon ^{4}$ och $|I|\approx k/\varepsilon ^{2}$ där $0\leq \varepsilon$ , uppnår algoritmen Frobenius error bound $\|A-CUR\|_{F}\leq \|A-A_{k}\|_{F}+\varepsilon \|A\ |_{F}$ , där $A_{k}$ är den optimala rankningen k approximation.

Tensor

Tensor-CURT-nedbrytning är en generalisering av matris-CUR-nedbrytning. Formellt är en CURT-tensorapproximation av en tensor A tre matriser och en (kärn-)tensor C , R , T och U så att C är gjord av kolumner av A , R är gjord av rader av A , T är gjord av rör av A och att produkten U(C,R,T) (där $i,j,l$ -e posten i den är ${\displaystyle \sum _{i',j',l'}U_{i',j',l'}C_{i ,i'}R_{j,j'}T_{l,l'}})$ är nära A . Vanligtvis väljs CURT för att vara en rank - k approximation, vilket betyder att C innehåller k kolumner av A , R innehåller k rader av A , T innehåller rör av A och U är en k -by- k -by- k (kärna -) tensor.

Se även

• dimensionsreduktion