Aproximação de posto baixo
Em matemática, a aproximação de posto baixo é 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 a uma restrição de que a matriz de aproximação tenha posto reduzido. 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 há outras restrições na matriz de aproximação além da restrição de posto, por exemplo, não negatividade e estrutura de Hankel.
A aproximação de posto baixo está intimamente relacionada com:
- análise de componentes principais,
- análise fatorial,
- mínimos quadrados totais,
- análise semântica latente,
- regressão ortogonal, e
- decomposição em modos dinâmicos
Definição
Dados
- uma especificação de estrutura ,
- um vetor de parâmetros de estrutura ,
- uma norma , e
- o posto desejado ,
Aplicações
- Identificação de sistema linear, caso em que a matriz de aproximação é estruturada por Hankel.[1][2]
- Aprendizado de máquina, caso em que a matriz de aproximação é estruturada de forma não linear.[3]
- Sistemas de recomendação, em que a matriz de dados tem valores faltantes e a aproximação é categórica.
- Completamento de matriz de distâncias, caso em que há uma restrição de que as matrizes sejam definidas positivas.
- Processamento de linguagem natural, caso em que a aproximação é não negativa.
- Álgebra computacional, caso em que a aproximação é estruturada por Sylvester.
Problema básico de aproximação de posto baixo
O problema não estruturado com ajuste medido pela norma de Frobenius, ou seja,
tem solução analítica em termos da decomposição em valores singulares da matriz de dados. O resultado é referido como o lema de aproximação de matrizes ou teorema de Eckart–Young–Mirsky. Este problema foi originalmente resolvido por Erhard Schmidt[4] no contexto de dimensão infinita de operadores integrais (embora seus métodos facilmente se generalizem para operadores compactos arbitrários em espaços de Hilbert) e posteriormente redescoberto por C. Eckart e G. Young.[5] L. Mirsky generalizou o resultado para normas arbitrárias unitariamente invariantes.[6] Sejam
a decomposição em valores singulares de e partição , , e como segue:
em que é , é , e é . Então a matriz de posto-, obtida a partir da decomposição em valores singulares truncada
é tal que
O minimizador é único se, e somente se, .
Prova do teorema de Eckart–Young–Mirsky (para a norma espectral)
Seja uma matriz real (possivelmente retangular) com . Suponha que
é a decomposição em valores singulares de . Lembre-se que e são matrizes ortogonais, e é uma matriz diagonal com entradas tais que .
Afirmamos que a melhor aproximação de posto de na norma espectral, denotada por , é dada por
em que e denotam as -ésimas colunas de e , respectivamente.
Primeiro, note que temos
Portanto, precisamos mostrar que se , em que e têm colunas, então .
Como tem colunas, então deve haver uma combinação linear não trivial das primeiras colunas de , ou seja,
tal que . Sem perda de generalidade, podemos escalar de modo que ou (equivalentemente) . Portanto,
O resultado segue tomando a raiz quadrada de ambos os lados da desigualdade acima.
Prova do teorema de Eckart–Young–Mirsky (para a norma de Frobenius)
Seja uma matriz real (possivelmente retangular) com . Suponha que
é a decomposição em valores singulares de .
Afirmamos que a melhor aproximação de posto de na norma de Frobenius, denotada por , é dada por
em que e denotam as -ésimas colunas de e , respectivamente.
Primeiro, note que temos
Portanto, precisamos mostrar que se , com e tendo colunas, então
Pela desigualdade triangular com a norma espectral, se então . Suponha que e denotam respectivamente as aproximações de posto de e pelo método SVD descrito acima. Então, para qualquer
Como , quando e concluímos que para
Portanto,
como desejado.
Problemas de aproximação de posto baixo 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 posto baixo ponderada
em que vetoriza a matriz por colunas e é uma matriz de peso positiva (semi-)definida dada.
O problema geral de aproximação de posto baixo ponderada não admite uma solução analítica em termos de decomposição de valores singulares e é resolvido por métodos de otimização local, que não garantem que uma solução global ótima seja encontrada.
No caso de pesos não correlacionados, o problema de aproximação de posto baixo ponderada também pode ser formulado desta forma:[7][8] para uma matriz não negativa e uma matriz queremos minimizar sobre matrizes , de posto no máximo .
Problemas de aproximação de posto baixo por entradas
Seja . Para , o algoritmo mais rápido é executado em tempo .[9][10] Uma das ideias importantes usadas é chamada de Oblivious Subspace Embedding (OSE), proposta pela primeira vez por Sarlos.[11]
Para , sabe-se que esta norma L1 por entradas é mais robusta do que a norma de Frobenius na presença de outliers e é indicada em modelos para os quais as suposições gaussianas sobre o ruído podem não se aplicar. É natural procurar minimizar .[12] Para e , existem alguns algoritmos com garantias prováveis.[13][14]
Problema de aproximação de posto baixo de distâncias
Sejam e dois conjuntos de pontos em um espaço métrico arbitrário. Seja uma matriz em que . Tais matrizes de distâncias são comumente calculadas em pacotes de software e têm aplicações para aprendizado de variedades de imagens, reconhecimento de escrita manual e desdobramento multidimensional. Na tentativa de reduzir seu tamanho de descrição,[15][16] pode-se estudar uma aproximação de posto baixo de tais matrizes.
Problema de aproximação de posto baixo distribuído/em streaming
Os problemas de aproximação de posto baixo nos modelos distribuídos e de streaming foram considerados por Boutsidis et al.[17]
Representações por imagem e núcleo das restrições de posto
Usando as equivalências
e
o problema de aproximação de posto baixo ponderada torna-se equivalente aos problemas de otimização de parâmetros
e
em que é a matriz identidade de tamanho .
Algoritmo de projeções alternadas
A representação por imagem da restrição de posto sugere um método de otimização de parâmetros 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 de e seja um problema de otimização biconvexo difícil, a minimização sobre uma das variáveis sozinha é um problema linear de mínimos quadrados e pode ser resolvida globalmente e eficientemente.
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 posto baixo ponderada. O valor inicial para (ou ) deve ser fornecido. A iteração é interrompida quando uma condição de convergência definida pelo usuário é satisfeita.
O algoritmo de projeções alternadas para aproximação de posto baixo ponderada pode ser implementado em Matlab da seguinte forma:
function [dh, f] = wlra_ap(d, w, p, tol, maxiter) [m, n] = size(d); r = size(p, 2); f = inf; for i = 2:maxiter % minimização sobre L bp = kron(eye(n), p); vl = (bp' * w * bp) \ bp' * w * d(:); l = reshape(vl, r, n); % minimização sobre P bl = kron(l', eye(m)); vp = (bl' * w * bl) \ bl' * w * d(:); p = reshape(vp, m, r); % verificação da condição de parada 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 posto baixo, parametrizado na forma da imagem, é bilinear nas variáveis ou . A natureza bilinear do problema é efetivamente utilizada em uma abordagem alternativa, chamada de projeções variáveis.[18]
Considere novamente o problema de aproximação de posto baixo ponderada, parametrizado na forma da imagem. A minimização em relação à variável (um problema linear de mínimos quadrados) leva à expressão de forma fechada do erro de aproximação em função de
O problema original é, portanto, equivalente ao problema não linear de mínimos quadrados 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.
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 também pode ser aplicada a problemas de aproximação de posto baixo 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 deixadas no estágio de minimização não linear por mínimos quadrados. Tais problemas ocorrem na identificação do sistema, parametrizado na forma de kernel, onde as variáveis eliminadas são a trajetória de aproximação e as variáveis restantes 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 posto baixo restrita convexa
Normalmente, queremos que nossa nova solução não seja apenas de posto baixo, mas também satisfaça outras restrições convexas devido aos requisitos da aplicação. Nosso problema de interesse seria o seguinte,
Este problema tem muitas aplicações no mundo real, inclusive para recuperar uma boa solução de um relaxamento inexato (programação semidefinida). Se restrição adicional é linear, tal como quando se exige que todos os elementos sejam não-negativos, o problema é chamado de aproximação estruturada de posto baixo.[19] A forma mais geral é chamada de aproximação de posto baixo restrita convexa.
Este problema é útil para resolver muitos problemas. No entanto, é um desafio devido à combinação das restrições convexas e não convexas (posto baixo). Diferentes técnicas foram desenvolvidas com base em diferentes realizações de . No entanto, o Método de Multiplicadores de Direção Alternada (ADMM) pode ser aplicado para resolver o problema não convexo com função objetivo convexa, restrições de posto e outras restrições convexas,[20] e, portanto, é adequado para resolver nosso problema acima. Além disso, diferentemente dos problemas gerais não convexos, o ADMM garantirá a convergência de uma solução viável desde que sua variável dual convirja nas iterações.
Ver também
- A aproximação matricial CUR é feita a partir das linhas e colunas da matriz original
Referências
- ↑ I. Markovsky, Structured low-rank approximation and its applications, Automatica, Volume 44, Issue 4, April 2008, Pages 891–909. doi:10.1016/j.automatica.2007.09.011
- ↑ I. Markovsky, J. C. Willems, S. Van Huffel, B. De Moor, and R. Pintelon, Application of structured total least squares for system identification and model reduction. IEEE Transactions on Automatic Control, Volume 50, Number 10, 2005, pages 1490–1500.
- ↑ I. Markovsky, Low-Rank Approximation: Algorithms, Implementation, Applications, Springer, 2012, ISBN 978-1-4471-2226-5
- ↑ E. Schmidt, Zur Theorie der linearen und nichtlinearen Integralgleichungen, Math. Annalen 63 (1907), 433-476. doi:10.1007/BF01449770
- ↑ C. Eckart, G. Young, The approximation of one matrix by another of lower rank. Psychometrika, Volume 1, 1936, Pages 211–8. doi:10.1007/BF02288367
- ↑ L. Mirsky, Symmetric gauge functions and unitarily invariant norms, Q.J. Math. 11 (1960), 50-59. doi:10.1093/qmath/11.1.50
- ↑ Srebro, Nathan; Jaakkola, Tommi (2003). Weighted Low-Rank Approximations (PDF). ICML'03
- ↑ Razenshteyn, Ilya; Song, Zhao; Woodruff, David P. (2016). Weighted Low Rank Approximations with Provable Guarantees. STOC '16 Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
- ↑ Clarkson, Kenneth L.; Woodruff, David P. (2013). Low Rank Approximation and Regression in Input Sparsity Time. STOC '13 Proceedings of the forty-fifth annual ACM symposium on Theory of Computing. arXiv:1207.6365
- ↑ Nelson, Jelani; Nguyen, Huy L. (2013). OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. FOCS '13. arXiv:1211.1002
- ↑ Sarlos, Tamas (2006). Improved approximation algorithms for large matrices via random projections. FOCS'06
- ↑ Song, Zhao; Woodruff, David P.; Zhong, Peilin (2017). Low Rank Approximation with Entrywise L1-Norm Error. STOC '17 Proceedings of the forty-ninth annual ACM symposium on Theory of Computing. arXiv:1611.00898
- ↑ Bringmann, Karl; Kolev, Pavel; Woodruff, David P. (2017). Approximation Algorithms for L0-Low Rank Approximation. NIPS'17. arXiv:1710.11253
- ↑ Chierichetti, Flavio; Gollapudi, Sreenivas; Kumar, Ravi; Lattanzi, Silvio; Panigrahy, Rina; Woodruff, David P. (2017). Algorithms for Lp Low-Rank Approximation. ICML'17. arXiv:1705.06730
- ↑ Bakshi, Ainesh L.; Woodruff, David P. (2018). Sublinear Time Low-Rank Approximation of Distance Matrices. NeurIPS. arXiv:1809.06986
- ↑ Indyk, Piotr; Vakilian, Ali; Wagner, Tal; Woodruff, David P. (2019). Sample-Optimal Low-Rank Approximation of Distance Matrices. COLT
- ↑ Boutsidis, Christos; Woodruff, David P.; Zhong, Peilin (2016). Optimal Principal Component Analysis in Distributed and Streaming Models. STOC. arXiv:1504.06729
- ↑ G. Golub and V. Pereyra, Separable nonlinear least squares: the variable projection method and its applications, Institute of Physics, Inverse Problems, Volume 19, 2003, Pages 1-26.
- ↑ Chu, Moody T.; Funderlic, Robert E.; Plemmons, Robert J. (2003). «structured low-rank approximation». Linear Algebra and Its Applications. 366: 157–172. doi:10.1016/S0024-3795(02)00505-0
- ↑ «A General System for Heuristic Solution of Convex Problems over Nonconvex Sets» (PDF)
- MT Chu, RE Funderlic, RJ Plemmons, Aproximação estruturada de baixo escalão, Álgebra Linear e suas Aplicações, Volume 366, 1º de junho de 2003, Páginas 157–172doi:10.1016/S0024-3795(02)00505-0
Ligações externas
- Pacote C++ para aproximação de posto baixo estruturada