Frequency Component Recovery From Spectrum Measurements

In this work, we present some novel results for recovering the frequency components (frequencies and their complex coefficients) of an <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>-dimensional complex signal/vector from noiseless measurements of its frequency spectrum. In the first part of the work, the frequency vectors are the general Vandermonde vectors (with an amplitude varying exponentially across the vector components) and the spectrum is a “Vandermonde” spectrum (a vector’s Vandermonde transform). It is shown that if the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>-dimensional vector is composed of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</i> unknown frequency components, exact recovery of the frequency components is possible with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2s$ </tex-math></inline-formula> uniform measurements of the spectrum and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\mathrm {poly}(s))$ </tex-math></inline-formula> complexity when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n \geq 2s$ </tex-math></inline-formula>. Furthermore, exact recovery with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\mathrm {poly}(s))$ </tex-math></inline-formula> complexity is also possible with arbitrary <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$3s$ </tex-math></inline-formula> non-uniform measurements of the spectrum. In the second part of the work, the frequency vectors are Fourier vectors and we consider the challenging problem of recovering the frequency components from <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">phase-less</i> Fourier spectrum measurements. One main result shows that the frequencies of the vector can be recovered with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$4s - 1$ </tex-math></inline-formula> uniform spectrum measurements and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\mathrm {poly}(s))$ </tex-math></inline-formula> complexity if <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n \geq 4s - 1$ </tex-math></inline-formula>, but not their complex coefficients (there being in general <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2^{s-1}$ </tex-math></inline-formula> solutions for the coefficients). Another main result shows the surprising fact that if the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>-dimensional vector is composed of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</i> unknown frequency components with at least one having a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">non-harmonic</i> frequency, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n \geq 4s - 1$ </tex-math></inline-formula> and we take <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$8s-3$ </tex-math></inline-formula> non-uniform (phase-less) spectrum measurements, the frequencies can be recovered exactly while, remarkably, there are <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">only two</i> possible coefficient vectors (up to a phase) and they are easily obtainable from each other. The frequencies and the two coefficient vectors can be found by an algorithm with only <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\mathrm {poly}(s))$ </tex-math></inline-formula> complexity. Based on the results from the first part, a new class of compressed sensing measurement matrices is presented from which it is possible to recover <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</i>-sparse <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>-dimensional vectors for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n \geq 2s$ </tex-math></inline-formula> with as few as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2s$ </tex-math></inline-formula> measurements and with a recovery algorithm of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\mathrm {poly}(s))$ </tex-math></inline-formula> complexity. Similarly, from the results in the second part, we provide a class of measurement matrices from which it is possible to recover almost all <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</i>-sparse <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>-dimensional vectors (up to a phase) from <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$8s - 2$ </tex-math></inline-formula> phase-less measurements and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\mathrm {poly}(s))$ </tex-math></inline-formula> recovery complexity when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n \geq 4s - 1$ </tex-math></inline-formula>.