Phaseless PCA: Low-Rank Matrix Recovery from Column-wise Phaseless Measurements

Seyedehsara Nayer, Praneeth Narayanamurthy, Namrata Vaswani
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:4762-4770, 2019.

Abstract

This work proposes the first set of simple, practically useful, and provable algorithms for two inter-related problems. (i) The first is low-rank matrix recovery from magnitude-only (phaseless) linear projections of each of its columns. This finds important applications in phaseless dynamic imaging, e.g., Fourier Ptychographic imaging of live biological specimens. Our guarantee shows that, in the regime of small ranks, the sample complexity required is only a little larger than the order-optimal one, and much smaller than what standard (unstructured) phase retrieval methods need. %Moreover our algorithm is fast and memory-efficient if only the minimum required number of measurements is used (ii) The second problem we study is a dynamic extension of the above: it allows the low-dimensional subspace from which each image/signal (each column of the low-rank matrix) is generated to change with time. We introduce a simple algorithm that is provably correct as long as the subspace changes are piecewise constant.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-nayer19a, title = {Phaseless {PCA}: Low-Rank Matrix Recovery from Column-wise Phaseless Measurements}, author = {Nayer, Seyedehsara and Narayanamurthy, Praneeth and Vaswani, Namrata}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {4762--4770}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/nayer19a/nayer19a.pdf}, url = {https://proceedings.mlr.press/v97/nayer19a.html}, abstract = {This work proposes the first set of simple, practically useful, and provable algorithms for two inter-related problems. (i) The first is low-rank matrix recovery from magnitude-only (phaseless) linear projections of each of its columns. This finds important applications in phaseless dynamic imaging, e.g., Fourier Ptychographic imaging of live biological specimens. Our guarantee shows that, in the regime of small ranks, the sample complexity required is only a little larger than the order-optimal one, and much smaller than what standard (unstructured) phase retrieval methods need. %Moreover our algorithm is fast and memory-efficient if only the minimum required number of measurements is used (ii) The second problem we study is a dynamic extension of the above: it allows the low-dimensional subspace from which each image/signal (each column of the low-rank matrix) is generated to change with time. We introduce a simple algorithm that is provably correct as long as the subspace changes are piecewise constant.} }
Endnote
%0 Conference Paper %T Phaseless PCA: Low-Rank Matrix Recovery from Column-wise Phaseless Measurements %A Seyedehsara Nayer %A Praneeth Narayanamurthy %A Namrata Vaswani %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-nayer19a %I PMLR %P 4762--4770 %U https://proceedings.mlr.press/v97/nayer19a.html %V 97 %X This work proposes the first set of simple, practically useful, and provable algorithms for two inter-related problems. (i) The first is low-rank matrix recovery from magnitude-only (phaseless) linear projections of each of its columns. This finds important applications in phaseless dynamic imaging, e.g., Fourier Ptychographic imaging of live biological specimens. Our guarantee shows that, in the regime of small ranks, the sample complexity required is only a little larger than the order-optimal one, and much smaller than what standard (unstructured) phase retrieval methods need. %Moreover our algorithm is fast and memory-efficient if only the minimum required number of measurements is used (ii) The second problem we study is a dynamic extension of the above: it allows the low-dimensional subspace from which each image/signal (each column of the low-rank matrix) is generated to change with time. We introduce a simple algorithm that is provably correct as long as the subspace changes are piecewise constant.
APA
Nayer, S., Narayanamurthy, P. & Vaswani, N.. (2019). Phaseless PCA: Low-Rank Matrix Recovery from Column-wise Phaseless Measurements. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:4762-4770 Available from https://proceedings.mlr.press/v97/nayer19a.html.

Related Material