We consider the problem of approximating a given matrix by a low-rank matrix so as to minimize the entry-wise ℓp-approximation error, for any P ≥ 1; the case p = 2 is the classical SVD problem. We obtain the first provably good approximation algorithms for this version of low-rank approximation that work for every value of p ≥ 1, including p = σ. Our algorithms are simple, easy to implement, work well in practice, and illustrate interesting tradeoffs between the approximation quality, the running time, and the rank of the approximating matrix.

Algorithms for ℓp Low Rank Approximation / Chierichetti, Flavio; Gollapudi, Sreenivas; Kumar, Ravi; Lattanzi, Silvio; Panigrahy, Rina; Woodruff, David P.. - 70:(2017), pp. 806-814. (Intervento presentato al convegno 34th International Conference on Machine Learning tenutosi a Sydney; Australia).

Algorithms for ℓp Low Rank Approximation

CHIERICHETTI, FLAVIO
;
LATTANZI, SILVIO;
2017

Abstract

We consider the problem of approximating a given matrix by a low-rank matrix so as to minimize the entry-wise ℓp-approximation error, for any P ≥ 1; the case p = 2 is the classical SVD problem. We obtain the first provably good approximation algorithms for this version of low-rank approximation that work for every value of p ≥ 1, including p = σ. Our algorithms are simple, easy to implement, work well in practice, and illustrate interesting tradeoffs between the approximation quality, the running time, and the rank of the approximating matrix.
2017
34th International Conference on Machine Learning
Approximation theory, Artificial intelligence; Learning systems
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Algorithms for ℓp Low Rank Approximation / Chierichetti, Flavio; Gollapudi, Sreenivas; Kumar, Ravi; Lattanzi, Silvio; Panigrahy, Rina; Woodruff, David P.. - 70:(2017), pp. 806-814. (Intervento presentato al convegno 34th International Conference on Machine Learning tenutosi a Sydney; Australia).
File allegati a questo prodotto
File Dimensione Formato  
Chierichetti_Algorithms_2017.pdf

accesso aperto

Note: http://proceedings.mlr.press/v70/chierichetti17a/chierichetti17a.pdf
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 2.17 MB
Formato Adobe PDF
2.17 MB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1002074
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 0
social impact