2021/03/02 by Bendory, Tamir, Edidin, Dan, Kreymer, Shay
#FOS: Computer and information sciences #FOS: Electrical engineering #Information Theory (cs.IT) #Signal Processing (eess.SP) #electronic engineering #information engineering
paper · doi:10.48550/arxiv.2103.01551
The q-th order spectrum is a polynomial of degree q in the entries of a signal x∈ℂN, which is invariant under circular shifts of the signal. For q≥ 3, this polynomial determines the signal uniquely, up to a circular shift, and is called a high-order spectrum. The high-order spectra, and in particular the bispectrum (q=3) and the trispectrum (q=4), play a prominent role in various statistical signal processing and imaging applications, such as phase retrieval and single-particle reconstruction. However, the dimension of the q-th order spectrum is Nq-1, far exceeding the dimension of x, leading to increased computational load and storage requirements. In this work, we show that it is unnecessary to store and process the full high-order spectra: a signal can be characterized uniquely, up to symmetries, from only N+1 linear measurements of its high-order spectra. The proof relies on tools from algebraic geometry and is corroborated by numerical experiments.