Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation From Undersampled Data
dc.contributor.author | Zhang, Dejiao | |
dc.contributor.author | Balzano, Laura | |
dc.date.accessioned | 2022-02-21T01:47:53Z | |
dc.date.available | 2022-02-21T01:47:53Z | |
dc.date.issued | 2022-02-20 | |
dc.identifier.uri | https://hdl.handle.net/2027.42/171760 | en |
dc.description.abstract | Subspace learning and matrix factorization problems have great many applications in science and engineering, and efficient algorithms are critical as dataset sizes continue to grow. Many relevant problem formulations are non-convex, and in a variety of contexts it has been observed that solving the non-convex problem directly is not only efficient but reliably accurate. We discuss convergence theory for a particular method: first order incremental gradient descent constrained to the Grassmannian. The output of the algorithm is an orthonormal basis for a $d$-dimensional subspace spanned by an input streaming data matrix. We study two sampling cases: where each data vector of the streaming matrix is fully sampled, or where it is undersampled by a sampling matrix $A_t\in \mathbb{R}^{m\times n}$ with $m\ll n$. Our results cover two cases, where $A_t$ is Gaussian or a subset of rows of the identity matrix. We propose an adaptive stepsize scheme that depends only on the sampled data and algorithm outputs. We prove that with fully sampled data, the stepsize scheme maximizes the improvement of our convergence metric at each iteration, and this method converges from any random initialization to the true subspace, despite the non-convex formulation and orthogonality constraints. For the case of undersampled data, we establish monotonic expected improvement on the defined convergence metric for each iteration with high probability. | en_US |
dc.language.iso | en_US | en_US |
dc.rights | Attribution-NonCommercial-ShareAlike 4.0 International | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-sa/4.0/ | * |
dc.title | Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation From Undersampled Data | en_US |
dc.type | Technical Report | en_US |
dc.subject.hlbsecondlevel | Computer Science | |
dc.subject.hlbsecondlevel | Electrical Engineering | |
dc.subject.hlbtoplevel | Engineering | |
dc.contributor.affiliationumcampus | Ann Arbor | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/171760/4/GrouseCS-Feb2022.pdf | en |
dc.identifier.doi | https://dx.doi.org/10.7302/4151 | |
dc.description.depositor | SELF | en_US |
dc.working.doi | 10.7302/4151 | en_US |
dc.owningcollname | Electrical Engineering and Computer Science, Department of (EECS) |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.