Aproximação de classificação baixa - Low-rank approximation

Em matemática, a aproximação de classificação baixa é um problema de minimização , no qual a função de custo mede o ajuste entre uma dada matriz (os dados) e uma matriz de aproximação (a variável de otimização), sujeita à restrição de que a matriz de aproximação tem classificação reduzida . O problema é usado para modelagem matemática e compressão de dados . A restrição de classificação está relacionada a uma restrição na complexidade de um modelo que se ajusta aos dados. Em aplicações, muitas vezes existem outras restrições na matriz de aproximação além da restrição de classificação, por exemplo, não negatividade e estrutura de Hankel .

A aproximação de classificação inferior está intimamente relacionada a:

• análise de componentes principais ,
• análise fatorial ,
• mínimos quadrados totais ,
• análise semântica latente , e
• regressão ortogonal .

• decomposição de modo dinâmico

Dado

• especificação da estrutura ,${\ displaystyle {\ mathcal {S}}: \ mathbb {R} ^ {n_ {p}} \ to \ mathbb {R} ^ {m \ times n}}$
• vetor de parâmetros de estrutura ,${\ displaystyle p \ in \ mathbb {R} ^ {n_ {p}}}$
• norma , e${\ displaystyle \ | \ cdot \ |}$
• classificação desejada ,${\ displaystyle r}$

${\ displaystyle {\ text {minimize}} \ quad {\ text {over}} {\ widehat {p}} \ quad \ | p - {\ widehat {p}} \ | \ quad {\ text {assunto} } \ quad \ operatorname {rank} {\ big (} {\ mathcal {S}} ({\ widehat {p}}) {\ big)} \ leq r.}$

Formulários

• Identificação do sistema linear , caso em que a matriz de aproximação é estruturada de Hankel .
• Aprendizado de máquina , caso em que a matriz de aproximação é estruturada de forma não linear.
• Sistemas de recomendação , em que casos a matriz de dados possui valores ausentes e a aproximação é categórica .
• Conclusão da matriz de distância , caso em que há uma restrição de definição positiva.
• Processamento de linguagem natural , caso em que a aproximação é não negativa .
• Álgebra computacional , caso em que a aproximação é estruturada de Sylvester .

Problema básico de aproximação de baixa classificação

O problema não estruturado com ajuste medido pela norma Frobenius , ou seja,

${\ displaystyle {\ text {minimize}} \ quad {\ text {over}} {\ widehat {D}} \ quad \ | D - {\ widehat {D}} \ | _ {\ text {F}} \ quad {\ text {subject to}} \ quad \ operatorname {rank} {\ big (} {\ widehat {D}} {\ big)} \ leq r}$

tem solução analítica em termos da decomposição de valor singular da matriz de dados. O resultado é conhecido como lema de aproximação da matriz ou teorema de Eckart-Young-Mirsky . Deixar

${\ displaystyle D = U \ Sigma V ^ {\ top} \ in \ mathbb {R} ^ {m \ times n}, \ quad m \ geq n}$

ser a decomposição do valor singular da e de partição , e como se segue: ${\ displaystyle D}$${\ displaystyle U}$${\ displaystyle \ Sigma =: \ operatorname {diag} (\ sigma _ {1}, \ ldots, \ sigma _ {m})}$${\ displaystyle V}$

${\ displaystyle U =: {\ begin {bmatrix} U_ {1} & U_ {2} \ end {bmatrix}}, \ quad \ Sigma =: {\ begin {bmatrix} \ Sigma _ {1} & 0 \\ 0 & \ Sigma _ {2} \ end {bmatrix}}, \ quad {\ text {e}} \ quad V =: {\ begin {bmatrix} V_ {1} & V_ {2} \ end {bmatrix}},}$

onde está , está e está . Em seguida, a matriz de classificação , obtida a partir da decomposição de valor singular truncado ${\ displaystyle U_ {1}}$${\ displaystyle m \ times r}$${\ displaystyle \ Sigma _ {1}}$${\ displaystyle r \ times r}$${\ displaystyle V_ {1}}$${\ displaystyle n \ times r}$${\ displaystyle r}$

${\ displaystyle {\ widehat {D}} ^ {*} = U_ {1} \ Sigma _ {1} V_ {1} ^ {\ top},}$

é tal que

${\ displaystyle \ | D - {\ widehat {D}} ^ {*} \ | _ {\ text {F}} = \ min _ {\ operatorname {rank} ({\ widehat {D}}) \ leq r } \ | D - {\ widehat {D}} \ | _ {\ text {F}} = {\ sqrt {\ sigma _ {r + 1} ^ {2} + \ cdots + \ sigma _ {m} ^ {2}}}.}$

O minimizador é único se e somente se . ${\ displaystyle {\ widehat {D}} ^ {*}}$${\ displaystyle \ sigma _ {r + 1} \ neq \ sigma _ {r}}$

Prova do teorema de Eckart-Young-Mirsky (para norma espectral )

Let Ser uma matriz real (possivelmente retangular) com . Suponha que ${\ displaystyle A \ in \ mathbb {R} ^ {m \ times n}}$${\ displaystyle m \ geq n}$

${\ displaystyle A = U \ Sigma V ^ {\ top}}$

é a decomposição de valor singular de . Lembre-se de que e são matrizes ortogonais , e é uma matriz diagonal com entradas tais que . ${\ displaystyle A}$${\ displaystyle U}$${\ displaystyle V}$${\ displaystyle \ Sigma}$${\ displaystyle m \ times n}$ ${\ displaystyle (\ sigma _ {1}, \ sigma _ {2}, \ cdots, \ sigma _ {n})}$${\ displaystyle \ sigma _ {1} \ geq \ sigma _ {2} \ geq \ cdots \ geq \ sigma _ {n} \ geq 0}$

Afirmamos que a melhor aproximação de classificação na norma espectral, denotada por , é dada por ${\ displaystyle k}$${\ displaystyle A}$${\ displaystyle \ | \ cdot \ | _ {2}}$

${\ displaystyle A_ {k} = \ sum _ {i = 1} ^ {k} \ sigma _ {i} u_ {i} v_ {i} ^ {\ top}}$

onde e denotam a ésima coluna de e , respectivamente. ${\ displaystyle u_ {i}}$${\ displaystyle v_ {i}}$${\ displaystyle i}$${\ displaystyle U}$${\ displaystyle V}$

Primeiro, observe que temos

${\ displaystyle \ | A-A_ {k} \ | _ {2} = \ left \ | \ sum _ {i = k + 1} ^ {n} \ sigma _ {i} u_ {i} v_ {i} ^ {\ top} \ right \ | _ {2} = \ sigma _ {k + 1}}$

Portanto, precisamos mostrar que se onde e ter colunas então . ${\ displaystyle B_ {k} = XY ^ {\ top}}$${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle k}$${\ displaystyle \ | A-A_ {k} \ | _ {2} = \ sigma _ {k + 1} \ leq \ | A-B_ {k} \ | _ {2}}$

Uma vez que tem colunas, então deve haver uma combinação linear não trivial das primeiras colunas de , ou seja, ${\ displaystyle Y}$${\ displaystyle k}$${\ displaystyle k + 1}$${\ displaystyle V}$

${\ displaystyle w = \ gamma _ {1} v_ {1} + \ cdots + \ gamma _ {k + 1} v_ {k + 1},}$

tal que . Sem perda de generalidade, podemos dimensionar para que ou (equivalentemente) . Portanto, ${\ displaystyle Y ^ {\ top} w = 0}$${\ displaystyle w}$${\ displaystyle \ | w \ | _ {2} = 1}$${\ displaystyle \ gamma _ {1} ^ {2} + \ cdots + \ gamma _ {k + 1} ^ {2} = 1}$

${\ displaystyle \ | A-B_ {k} \ | _ {2} ^ {2} \ geq \ | (A-B_ {k}) w \ | _ {2} ^ {2} = \ | Aw \ | _ {2} ^ {2} = \ gamma _ {1} ^ {2} \ sigma _ {1} ^ {2} + \ cdots + \ gamma _ {k + 1} ^ {2} \ sigma _ {k +1} ^ {2} \ geq \ sigma _ {k + 1} ^ {2}.}$

O resultado segue tirando a raiz quadrada de ambos os lados da desigualdade acima.

Prova do teorema de Eckart-Young-Mirsky (para a norma de Frobenius )

Let Ser uma matriz real (possivelmente retangular) com . Suponha que ${\ displaystyle A \ in \ mathbb {R} ^ {m \ times n}}$${\ displaystyle m \ geq n}$

${\ displaystyle A = U \ Sigma V ^ {\ top}}$

é a decomposição de valor singular de . ${\ displaystyle A}$

Afirmamos que a melhor aproximação de classificação na norma Frobenius, denotada por , é dada por ${\ displaystyle k}$${\ displaystyle A}$${\ displaystyle \ | \ cdot \ | _ {F}}$

${\ displaystyle A_ {k} = \ sum _ {i = 1} ^ {k} \ sigma _ {i} u_ {i} v_ {i} ^ {\ top}}$

onde e denotam a ésima coluna de e , respectivamente. ${\ displaystyle u_ {i}}$${\ displaystyle v_ {i}}$${\ displaystyle i}$${\ displaystyle U}$${\ displaystyle V}$

Primeiro, observe que temos

${\ displaystyle \ | A-A_ {k} \ | _ {F} ^ {2} = \ left \ | \ sum _ {i = k + 1} ^ {n} \ sigma _ {i} u_ {i} v_ {i} ^ {\ top} \ right \ | _ {F} ^ {2} = \ sum _ {i = k + 1} ^ {n} \ sigma _ {i} ^ {2}}$

Portanto, precisamos mostrar que se onde e tiver colunas, então ${\ displaystyle B_ {k} = XY ^ {\ top}}$${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle k}$

${\ displaystyle \ | A-A_ {k} \ | _ {F} ^ {2} = \ sum _ {i = k + 1} ^ {n} \ sigma _ {i} ^ {2} \ leq \ | A-B_ {k} \ | _ {F} ^ {2}.}$

Pela desigualdade do triângulo com a norma espectral, se então . Suponha e denote respectivamente a aproximação de classificação para e pelo método SVD descrito acima. Então, para qualquer${\ displaystyle A = A '+ A' '}$${\ displaystyle \ sigma _ {1} (A) \ leq \ sigma _ {1} (A ') + \ sigma _ {1} (A' ')}$${\ displaystyle A '_ {k}}$${\ displaystyle A '' _ {k}}$${\ displaystyle k}$${\ displaystyle A '}$${\ displaystyle A ''}$${\ displaystyle i, j \ geq 1}$

${\ displaystyle {\ begin {alinhados} \ sigma _ {i} (A ') + \ sigma _ {j} (A' ') & = \ sigma _ {1} (A'-A' _ {i-1 }) + \ sigma _ {1} (A '' - A '' _ {j-1}) \\ & \ geq \ sigma _ {1} (A-A '_ {i-1} -A' ' _ {j-1}) \\ & \ geq \ sigma _ {1} (A-A_ {i + j-2}) \ qquad ({\ text {desde}} {\ rm {rank}} (A ' _ {i-1} + A '' _ {j-1}) \ leq {\ rm {posto \,}} (A_ {i + j-2})) \\ & = \ sigma _ {i + j -1} (A). \ End {alinhado}}}$

Desde , quando e concluímos que para${\ displaystyle \ sigma _ {k + 1} (B_ {k}) = 0}$${\ displaystyle A '= A-B_ {k}}$${\ displaystyle A '' = B_ {k}}$${\ displaystyle i \ geq 1, j = k + 1}$

${\ displaystyle \ sigma _ {i} (A-B_ {k}) \ geq \ sigma _ {k + i} (A).}$

Portanto,

${\ displaystyle \ | A-B_ {k} \ | _ {F} ^ {2} = \ sum _ {i = 1} ^ {n} \ sigma _ {i} (A-B_ {k}) ^ { 2} \ geq \ sum _ {i = k + 1} ^ {n} \ sigma _ {i} (A) ^ {2} = \ | A-A_ {k} \ | _ {F} ^ {2} ,}$

como requerido.

Problemas de aproximação de classificação baixa ponderada

A norma de Frobenius pondera uniformemente todos os elementos do erro de aproximação . O conhecimento prévio sobre a distribuição dos erros pode ser levado em consideração considerando o problema de aproximação de classificação baixa ponderada ${\ displaystyle D - {\ widehat {D}}}$

${\ displaystyle {\ text {minimize}} \ quad {\ text {over}} {\ widehat {D}} \ quad \ operatorname {vec} ^ {\ top} (D - {\ widehat {D}}) W \ operatorname {vec} (D - {\ widehat {D}}) \ quad {\ text {sujeito a}} \ quad \ operatorname {rank} ({\ widehat {D}}) \ leq r,}$

onde vetoriza a coluna da matriz e é uma dada matriz de peso positivo (semi) definido. ${\ displaystyle vec (A)}$ ${\ displaystyle A}$${\ displaystyle W}$

O problema geral de aproximação ponderada de baixo posto não admite uma solução analítica em termos de decomposição de valor singular e é resolvido por métodos de otimização local, que não fornecem garantia de que uma solução globalmente ótima seja encontrada.

No caso de pesos não correlacionados, o problema de aproximação de classificação baixa ponderada também pode ser formulado desta maneira: para uma matriz não negativa e uma matriz , queremos minimizar sobre matrizes,, de classificação no máximo . ${\ displaystyle W}$${\ displaystyle A}$${\ displaystyle \ sum _ {i, j} (W_ {i, j} (A_ {i, j} -B_ {i, j})) ^ {2}}$${\ displaystyle B}$${\ displaystyle r}$

Entrada-wise problemas de aproximação de baixo-rank${\ displaystyle L_ {p}}$

Deixe . Pois , o algoritmo mais rápido é executado no tempo. Uma das idéias importantes utilizadas é chamada Oblivious Subspace Embedding (OSE), proposta pela primeira vez por Sarlos. ${\ displaystyle \ | A \ | _ {p} = \ left (\ sum _ {i, j} | A_ {i, j} ^ {p} | \ right) ^ {1 / p}}$${\ displaystyle p = 2}$${\ displaystyle nnz (A) + n \ cdot poly (k / \ epsilon)}$

Pois , sabe-se que esta norma L1 de entrada é mais robusta do que a norma de Frobenius na presença de outliers e é indicada em modelos onde as suposições gaussianas sobre o ruído podem não se aplicar. É natural buscar minimizar . Para e , existem alguns algoritmos com garantias prováveis. ${\ displaystyle p = 1}$${\ displaystyle \ | BA \ | _ {1}}$${\ displaystyle p = 0}$${\ displaystyle p \ geq 1}$

Problema de aproximação de baixa classificação de distância

Deixe e seja dois conjuntos de pontos em um espaço métrico arbitrário. Deixe representar a matriz onde . Essas matrizes de distâncias são comumente calculadas em pacotes de software e têm aplicativos para aprendizado de coletores de imagens, reconhecimento de caligrafia e desdobramento multidimensional. Na tentativa de reduzir seu tamanho de descrição, pode-se estudar a aproximação de baixa classificação de tais matrizes. ${\ displaystyle P = \ {p_ {1}, \ ldots, p_ {m} \}}$${\ displaystyle Q = \ {q_ {1}, \ ldots, q_ {n} \}}$${\ displaystyle A}$${\ displaystyle m \ times n}$${\ displaystyle A_ {i, j} = dist (p_ {i}, q_ {i})}$

Problema de aproximação de classificação baixa distribuída / streaming

Os problemas de aproximação de baixa classificação na configuração distribuída e de streaming foram considerados em.

Representações de imagem e kernel das restrições de classificação

Usando as equivalências

${\ displaystyle \ operatorname {rank} ({\ widehat {D}}) \ leq r \ quad \ iff \ quad {\ text {há}} P \ in \ mathbb {R} ^ {m \ times r} { \ text {e}} L \ in \ mathbb {R} ^ {r \ vezes n} {\ text {tal que}} {\ widehat {D}} = PL}$

e

${\ displaystyle \ operatorname {rank} ({\ widehat {D}}) \ leq r \ quad \ iff \ quad {\ text {há um rank de linha completo}} R \ in \ mathbb {R} ^ {mr \ times m} {\ text {tal que}} R {\ widehat {D}} = 0}$

o problema de aproximação de classificação baixa ponderada torna-se equivalente aos problemas de otimização de parâmetro

${\ displaystyle {\ text {minimize}} \ quad {\ text {over}} {\ widehat {D}}, P {\ text {e}} L \ quad \ operatorname {vec} ^ {\ top} (D - {\ widehat {D}}) W \ operatorname {vec} (D - {\ widehat {D}}) \ quad {\ text {sujeito a}} \ quad {\ widehat {D}} = PL}$

e

${\ displaystyle {\ text {minimize}} \ quad {\ text {over}} {\ widehat {D}} {\ text {and}} R \ quad \ operatorname {vec} ^ {\ top} (D- { \ widehat {D}}) W \ operatorname {vec} (D - {\ widehat {D}}) \ quad {\ text {sujeito a}} \ quad R {\ widehat {D}} = 0 \ quad {\ texto {e}} \ quad RR ^ {\ top} = I_ {r},}$

onde está a matriz de identidade de tamanho . ${\ displaystyle I_ {r}}$${\ displaystyle r}$

Algoritmo de projeções alternadas

A representação da imagem da restrição de classificação sugere um método de otimização de parâmetro no qual a função de custo é minimizada alternativamente sobre uma das variáveis ​​( ou ) com a outra fixa. Embora a minimização simultânea sobre ambos e é um difícil otimização biconvex problema, minimização sobre uma das variáveis por si só é um linear de mínimos quadrados problema e pode ser resolvida globalmente e de forma eficiente. ${\ displaystyle P}$${\ displaystyle L}$${\ displaystyle P}$${\ displaystyle L}$

O algoritmo de otimização resultante (chamado de projeções alternadas) é globalmente convergente com uma taxa de convergência linear para uma solução localmente ótima do problema de aproximação de classificação baixa ponderada. O valor inicial para o parâmetro (ou ) deve ser fornecido. A iteração é interrompida quando uma condição de convergência definida pelo usuário é satisfeita. ${\ displaystyle P}$${\ displaystyle L}$

Implementação Matlab do algoritmo de projeções alternadas para aproximação ponderada de baixa classificação:

function [dh, f] = wlra_ap(d, w, p, tol, maxiter)
[m, n] = size(d); r = size(p, 2); f = inf;
for i = 2:maxiter
    % minimization over L
    bp = kron(eye(n), p);
    vl = (bp' * w * bp) \ bp' * w * d(:);
    l  = reshape(vl, r, n);
    % minimization over P
    bl = kron(l', eye(m));
    vp = (bl' * w * bl) \ bl' * w * d(:);
    p  = reshape(vp, m, r);
    % check exit condition
    dh = p * l; dd = d - dh;
    f(i) = dd(:)' * w * dd(:);
    if abs(f(i - 1) - f(i)) < tol, break, end
endfor

Algoritmo de projeções variáveis

O algoritmo de projeções alternadas explora o fato de que o problema de aproximação de baixo posto, parametrizado na forma de imagem, é bilinear nas variáveis ou . A natureza bilinear do problema é efetivamente usada em uma abordagem alternativa, chamada de projeções variáveis. ${\ displaystyle P}$${\ displaystyle L}$

Considere novamente o problema de aproximação de classificação baixa ponderada, parametrizado na forma de imagem. A minimização em relação à variável (um problema de mínimos quadrados lineares) leva à expressão de forma fechada do erro de aproximação como uma função de${\ displaystyle L}$${\ displaystyle P}$

${\ displaystyle f (P) = {\ sqrt {\ operatorname {vec} ^ {\ top} (D) {\ Big (} WW (I_ {n} \ otimes P) {\ big (} (I_ {n} \ otimes P) ^ {\ top} W (I_ {n} \ otimes P) {\ big)} ^ {- 1} (I_ {n} \ otimes P) ^ {\ top} W {\ Big)} \ operatorname {vec} (D)}}.}$

O problema original é, portanto, equivalente ao problema de mínimos quadrados não lineares de minimizar em relação a . Para este propósito, métodos de otimização padrão, por exemplo, o algoritmo de Levenberg-Marquardt podem ser usados. ${\ displaystyle f (P)}$${\ displaystyle P}$

Implementação Matlab do algoritmo de projeções variáveis ​​para aproximação ponderada de baixa classificação:

function [dh, f] = wlra_varpro(d, w, p, tol, maxiter)
prob = optimset(); prob.solver = 'lsqnonlin';
prob.options = optimset('MaxIter', maxiter, 'TolFun', tol); 
prob.x0 = p; prob.objective = @(p) cost_fun(p, d, w);
[p, f ] = lsqnonlin(prob); 
[f, vl] = cost_fun(p, d, w); 
dh = p * reshape(vl, size(p, 2), size(d, 2));

function [f, vl] = cost_fun(p, d, w)
bp = kron(eye(size(d, 2)), p);
vl = (bp' * w * bp) \ bp' * w * d(:);
f = d(:)' * w * (d(:) - bp * vl);

A abordagem de projeções variáveis ​​pode ser aplicada também a problemas de aproximação de classificação baixa parametrizados na forma de kernel. O método é eficaz quando o número de variáveis ​​eliminadas é muito maior do que o número de variáveis ​​de otimização restantes no estágio de minimização de mínimos quadrados não lineares. Tais problemas ocorrem na identificação do sistema, parametrizada na forma de kernel, onde as variáveis ​​eliminadas são a trajetória de aproximação e as demais variáveis ​​são os parâmetros do modelo. No contexto de sistemas lineares invariantes no tempo , a etapa de eliminação é equivalente à suavização de Kalman .

Uma variante: aproximação de classificação baixa restrita convexa

Normalmente, queremos que nossa nova solução não seja apenas de classificação baixa, mas também satisfaça outras restrições convexas devido aos requisitos do aplicativo. Nosso problema de interesse seria o seguinte,

${\ displaystyle {\ text {minimize}} \ quad {\ text {over}} {\ widehat {p}} \ quad \ | p - {\ widehat {p}} \ | \ quad {\ text {assunto} } \ quad \ operatorname {rank} {\ big (} {\ mathcal {S}} ({\ widehat {p}}) {\ big)} \ leq r {\ text {e}} g ({\ widehat { p}}) \ leq 0}$

Este problema tem muitas aplicações do mundo real, incluindo a recuperação de uma boa solução de um relaxamento inexato (programação semidefinida). Se a restrição adicional for linear, como exigimos que todos os elementos sejam não negativos, o problema é chamado de aproximação estruturada de baixa classificação. A forma mais geral é chamada de aproximação de classificação baixa restrita convexa. ${\ displaystyle g ({\ widehat {p}}) \ leq 0}$

Este problema é útil para resolver muitos problemas. No entanto, é um desafio devido à combinação das restrições convexa e não convexa (baixa classificação). Diferentes técnicas foram desenvolvidas com base em diferentes realizações de . No entanto, o Método dos Multiplicadores de Direção Alternada (ADMM) pode ser aplicado para resolver o problema não convexo com função objetivo convexa, restrições de classificação e outras restrições convexas e, portanto, é adequado para resolver nosso problema acima. Além disso, ao contrário dos problemas não convexos gerais, ADMM garantirá convergir uma solução viável, desde que sua variável dupla converta nas iterações ${\ displaystyle g ({\ widehat {p}}) \ leq 0}$

Veja também

• A aproximação da matriz CUR é feita a partir das linhas e colunas da matriz original

Referências

• MT Chu, RE Funderlic, RJ Plemmons, Structured low-rank aproximation, Linear Algebra and its Applications, Volume 366, 1 de junho de 2003, Páginas 157–172 doi : 10.1016 / S0024-3795 (02) 00505-0

links externos

• Pacote C ++ para aproximação estruturada de baixa classificação