Degree Type

Dissertation

Date of Award

2021

Degree Name

Doctor of Philosophy

Department

Electrical and Computer Engineering

Major

Electrical Engineering( Communicationsand Signal Processing)

First Advisor

Namrata Vaswani

Abstract

We study the Low Rank Phase Retrieval (LRPR) problem defined as follows: recover an $n \times q$ matrix $\Xstar$ of rank $r$ from a different and independent set of $m$ phaseless (magnitude-only) linear projections of each of its columns. To be precise, we need to recover $\Xstar$ from $\y_k := |\A_k{}' \xstar_k|, k=1,2,\dots, q$ when the measurement matrices $\A_k$ are mutually independent. Here $\y_k$ is an $m$ length vector, $\A_k$ is an $n \times m$ matrix, and $'$ denotes matrix transpose. The question is when can we solve LRPR with $m \ll n$? A reliable solution can enable fast and low-cost phaseless dynamic imaging, e.g., Fourier ptychographic imaging of live biological specimens. In this work, we develop first provably correct approaches for solving this LRPR problem. Our guarantee shows that the proposed algorithm solves LRPR to $\epsilon$ accuracy, with high probability, as long as $m q \ge C n r^3 \log(1/\epsilon)$, the matrices $\A_k$ contain i.i.d. standard Gaussian entries, and the right singular vectors of $\Xstar$ satisfy the incoherence assumption from matrix completion literature. Here $C$ is a numerical constant that only depends on the condition number of $\Xstar$ and on its incoherence parameter. Its time complexity is only $ C mq nr \log^2(1/\epsilon)$. We introduce a simple extension of our results for the dynamic LRPR setting as well.

We also develop a federated solution to recover an $n \times q$ rank-$r$ matrix, $\Xstar =[\xstar_1 , \xstar_2 ,...\xstar_q]$, from $m$ independent linear projections of each of its columns, i.e., from $\y_k := \A_k \x_k^* , k \in [q]$, where $\y_k$ is an $m$-length vector. Even though low-rank recovery problems have been extensively studied in the last decade, this particular problem has received surprisingly little attention. There exist only two provable solutions with a reasonable sample complexity, both of which are slow, have sub-optimal sample-complexity, and cannot be federated efficiently.

We introduce a novel gradient descent (GD) based solution called GD-min that needs only $\Omega((n+q) r^2 \log(1/\epsilon))$ samples and $O( mq nr \log (1/\epsilon))$ time to obtain an $\epsilon$-accurate estimate. Based on comparison with other well-studied problems, this is the best achievable sample complexity guarantee for a non-convex solution to the above problem. The time complexity is nearly linear and cannot be improved significantly either. Finally, in a federated setting, our solution has low communication cost and maintains privacy of the nodes' data and of the corresponding column estimates.

DOI

https://doi.org/10.31274/etd-20210609-131

Copyright Owner

Seyedehsara Nayer

Language

en

File Format

application/pdf

File Size

248 pages

Available for download on Tuesday, December 07, 2021

Share

COinS