Eigenvector phase retrieval: recovering eigenvectors from the absolute value of their entries

DOI10.1016/J.LAA.2022.08.002MaRDI QIDQ2168926zbMATH OpenOpenAlexWikidataFDO

Authors Stefan Steinerberger, H.-T. Wu

Publication date 26 August 2022

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.11143

zbMATH Keywords

eigenvector phase retrievalphase retrievalsynchronization

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Iterative numerical methods for linear systems (65F10) Randomized algorithms (68W20) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We consider the eigenvalue problem $Ax=lambdax$ where $Ainmathbb{R}^{nimesn}$ and the eigenvalue is also real $lambdainmathbbR$. If we are given $A$, $lambda$ and, additionally, the absolute value of the entries of $x$ (the vector $(|x_i|{)}_{i=1}^n$), is there a fast way to recover $x$? In particular, can this be done quicker than computing $x$ from scratch? This may be understood as a special case of the phase retrieval problem. We present a randomized algorithm which provably converges in expectation whenever $lambda$ is a simple eigenvalue. The problem should become easier when $|lambda|$ is large and we discuss another algorithm for that case as well.

Recommendations

• A geometric analysis of phase retrieval
• Entrywise eigenvector analysis of random matrices with low expected rank
• Phase retrieval via Wirtinger flow: theory and algorithms
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Phase retrieval with PhaseLift algorithm

Cites work

• A geometric analysis of phase retrieval
• A randomized Kaczmarz algorithm with exponential convergence
• An algorithm for Komlós conjecture matching Banaszczyk's bound
• Eigenvectors from eigenvalues: a survey of a basic identity in linear algebra
• Geometry of the phase retrieval problem. Graveyard of algorithms
• scientific article; zbMATH DE number 734955 (Why is no real title available?)
• scientific article; zbMATH DE number 1380581 (Why is no real title available?)
• Phase retrieval for the Cauchy wavelet transform
• Phase retrieval via randomized Kaczmarz: theoretical guarantees
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Randomized Kaczmarz Converges Along Small Singular Vectors
• Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
• The Gram-Schmidt walk: a cure for the Banaszczyk blues

Cited in

(1)

• Phase retrieval from local measurements: improved robustness via eigenvector-based angular synchronization

This page was built for publication: Eigenvector phase retrieval: recovering eigenvectors from the absolute value of their entries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2168926)