Active Positive Semidefinite Matrix Completion: Algorithms, Theory and Applications

Aniruddha Bhargava, Ravi Ganti, Rob Nowak
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:1349-1357, 2017.

Abstract

In this paper we provide simple, computationally efficient, active algorithms for completion of symmetric positive semidefinite matrices. Our proposed algorithms are based on adaptive Nyström sampling, and are allowed to actively query any element in the matrix, and obtain a possibly noisy estimate of the queried element. We establish sample complexity guarantees on the recovery of the matrix in the max-norm and in the process establish new theoretical results, potentially of independent interest, on adaptive Nyström sampling. We demonstrate the efficacy of our algorithms on problems in multi-armed bandits and kernel dimensionality reduction.

Cite this Paper

BibTeX
@InProceedings{pmlr-v54-bhargava17a, title = {{Active Positive Semidefinite Matrix Completion: Algorithms, Theory and Applications}}, author = {Bhargava, Aniruddha and Ganti, Ravi and Nowak, Rob}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {1349--1357}, year = {2017}, editor = {Singh, Aarti and Zhu, Jerry}, volume = {54}, series = {Proceedings of Machine Learning Research}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/bhargava17a/bhargava17a.pdf}, url = {https://proceedings.mlr.press/v54/bhargava17a.html}, abstract = {In this paper we provide simple, computationally efficient, active algorithms for completion of symmetric positive semidefinite matrices. Our proposed algorithms are based on adaptive Nyström sampling, and are allowed to actively query any element in the matrix, and obtain a possibly noisy estimate of the queried element. We establish sample complexity guarantees on the recovery of the matrix in the max-norm and in the process establish new theoretical results, potentially of independent interest, on adaptive Nyström sampling. We demonstrate the efficacy of our algorithms on problems in multi-armed bandits and kernel dimensionality reduction.} }
Endnote
%0 Conference Paper %T Active Positive Semidefinite Matrix Completion: Algorithms, Theory and Applications %A Aniruddha Bhargava %A Ravi Ganti %A Rob Nowak %B Proceedings of the 20th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2017 %E Aarti Singh %E Jerry Zhu %F pmlr-v54-bhargava17a %I PMLR %P 1349--1357 %U https://proceedings.mlr.press/v54/bhargava17a.html %V 54 %X In this paper we provide simple, computationally efficient, active algorithms for completion of symmetric positive semidefinite matrices. Our proposed algorithms are based on adaptive Nyström sampling, and are allowed to actively query any element in the matrix, and obtain a possibly noisy estimate of the queried element. We establish sample complexity guarantees on the recovery of the matrix in the max-norm and in the process establish new theoretical results, potentially of independent interest, on adaptive Nyström sampling. We demonstrate the efficacy of our algorithms on problems in multi-armed bandits and kernel dimensionality reduction.
APA
Bhargava, A., Ganti, R. & Nowak, R.. (2017). Active Positive Semidefinite Matrix Completion: Algorithms, Theory and Applications. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 54:1349-1357 Available from https://proceedings.mlr.press/v54/bhargava17a.html.

Related Material