Minimax Rank-$1$ Matrix Factorization

Venkatesh Saligrama, Alexander Olshevsky, Julien Hendrickx
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:3426-3436, 2020.

Abstract

We consider the problem of recovering a rank-one 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 small-perturbation 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-saligrama20a, title = {Minimax Rank-$1$ Matrix Factorization}, author = {Saligrama, Venkatesh and Olshevsky, Alexander and Hendrickx, Julien}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {3426--3436}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/saligrama20a/saligrama20a.pdf}, url = {https://proceedings.mlr.press/v108/saligrama20a.html}, abstract = {We consider the problem of recovering a rank-one 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 small-perturbation 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.} }
Endnote
%0 Conference Paper %T Minimax Rank-$1$ Matrix Factorization %A Venkatesh Saligrama %A Alexander Olshevsky %A Julien Hendrickx %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-saligrama20a %I PMLR %P 3426--3436 %U https://proceedings.mlr.press/v108/saligrama20a.html %V 108 %X We consider the problem of recovering a rank-one 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 small-perturbation 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.
APA
Saligrama, V., Olshevsky, A. & Hendrickx, J.. (2020). Minimax Rank-$1$ Matrix Factorization. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:3426-3436 Available from https://proceedings.mlr.press/v108/saligrama20a.html.

Related Material