MinimaxRank-1Factorization

Hendrickx, Julien;Olshevsky, Alex;Saligrama, venkatesh
(2020) 23rd International Conference on Artificial Intelligence and Statistics (AISTATS2020) — Location: Palermo, Sicily, Italy (3.June.2020)

Files

HOS_19_rank1.pdf
  • Open Access
  • Adobe PDF
  • 349.13 KB
Download

Details

Authors
  • Hendrickx, Julienorcid-logoUCLouvain
    Author
  • Olshevsky, AlexDepartment of Electrical and Computer Engineering, Boston University, USA
    Author
  • Saligrama, venkateshDepartment of Electrical and Computer Engineering, Boston University, USA
    Author
Abstract
(en) We consider the problem of recovering a rankone matrix when a perturbed subset of its entries is revealed. We propose a method based on least squares in the log-space and show its performance matches the lower bounds that we derive for this problem in the smallperturbation regime, which are related to the spectral gap of a graph representing the revealed entries. Unfortunately, we show that for larger disturbances, potentially exponentially growing errors are unavoidable for any consistent recovery method. We then propose a second algorithm relying on encoding the matrix factorization in the stationary distribution of a certain Markov chain. We show that, under the stronger assumption of known upper and lower bounds on the entries of the true matrix, this second method does not have exponential error growth for large disturbances. Both algorithms can be implemented in nearly linear time.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Hendrickx, J., Olshevsky, A., & Saligrama, v. (2020). MinimaxRank-1Factorization. Accepted/in-press. 23rd International Conference on Artificial Intelligence and Statistics (AISTATS2020), Palermo, Sicily, Italy. https://hdl.handle.net/2078.5/254782