In signal processing and system identification, we often face a frustrating trade-off: we can either use simple linear methods that fail on complex, non-convex problems, or we can use iterative optimization methods that are prone to getting stuck in local minima. A growing body of research suggests a third way. By reframing reconstruction problems—such as phase retrieval, sparse recovery, and system identification—as tasks of algebraic root-finding, researchers are developing deterministic algorithms that reach theoretical limits where traditional optimization fails.
The Prony Intuition: From Samples to Roots
The foundation of this approach is a centuries-old technique called Prony’s method. At its heart, it recognizes that many signals—like a sum of sinusoids or a sequence of spikes—possess an underlying algebraic structure. If a signal is sparse, its parameters can be viewed as the roots of a specific "characteristic" polynomial.
As Katz et al. demonstrate, this method is far more powerful than its reputation for numerical instability suggests. By constructing Hankel matrices from noisy data, one can derive the coefficients of a polynomial whose roots are the signal's locations. Katz et al. prove that this algebraic approach is actually min-max optimal for super-resolution, achieving the fundamental mathematical limits of accuracy for recovering closely spaced spikes.
This "root-matching" intuition extends to more complex structures. For instance, Batenkov and Yomdin show that the jump locations in piecewise smooth functions can be recovered by treating them as roots of algebraic equations derived from Fourier data. Similarly, Jin et al. use Prony’s method to resolve collisions in sparse convolution, treating the recovery of signal values as a sparse polynomial interpolation problem.
Bypassing Local Minima in Phase Retrieval
Phase retrieval—the task of recovering a signal from only the magnitude of its measurements—is notoriously non-convex. Traditional methods like "Charge Flipping" or gradient descent often stall in local minima. Algebraic methods sidestep this by "algebraizing" the measurement process.
Király and Ehler argue that phase retrieval is essentially a problem of pure algebraic geometry. By mapping measurement intensities to polynomial ideals, they show that signals can be recovered exactly at the theoretical identifiability threshold—a point where convex relaxation methods typically require significantly more data to succeed.
Other researchers use the specific structure of the measurement window to simplify the algebra. Cheng et al. propose a deterministic strategy for Short-Time Fourier Transform (STFT) measurements that propagates phase differences across a connectivity graph, avoiding the convergence issues of iterative solvers. In the domain of attosecond physics, Raz et al. and the authors show that treating pulses as "vectorial" signals allows one to match roots across spectral components, systematically eliminating the mathematical ambiguities that usually plague one-dimensional phase retrieval.
System Identification as an Eigenproblem
The same algebraic philosophy applies to understanding dynamical systems. Identifying the parameters of a Linear Dynamical System (LDS) is usually a difficult non-convex task. However, if we only care about the system's behavior (its eigenvalues), we can use the correspondence between LDS and ARMA models.
Hsu et al. demonstrate that the autoregressive coefficients of an ARMA model are exactly the coefficients of the system's characteristic polynomial. This allows for the recovery of a system's eigenspectrum using simple linear regression rather than expensive state-space identification. For noncausal models, Kusaka et al. show that these parameters can be extracted from the eigenvectors of a cumulant-based matrix, providing a stable solution even when system poles are near the unit circle.
When systems are defined by physical parameters, Komatsu et al. use Gröbner bases and algebraic elimination to map "black-box" models back to their physical "gray-box" origins. This approach achieves extreme numerical precision, bypassing the local minima that trap iterative gradient-based identification.
Reaching the Sparsity Limit
Finally, algebraic methods are pushing the boundaries of sparse recovery. Standard tools like Basis Pursuit are limited by the "mutual coherence" of the dictionary. Dragotti et al. and Lu et al. introduce ProSparse, which leverages the algebraic structure of Fourier and local bases. By solving systems of polynomial equations derived from a small number of consecutive samples, ProSparse can recover signals at sparsity levels where convex optimization fails, effectively reaching the theoretical uniqueness limit.
By treating signals not just as vectors of numbers, but as manifestations of underlying algebraic structures, these methods provide a robust, deterministic alternative to the uncertainties of iterative optimization. The reader should see that when we can find a polynomial whose roots are our targets, the complexity of the search space collapses into the stability of linear algebra.
Key Foundational Work
Blind Identification Using Higher Order Statistics and Eigendecomposition (1996) — contributed 2 concept elements to this direction.
Vectorial Phase Retrieval for Linear Characterization of Attosecond Pulses (2011) — contributed 1 concept elements to this direction.