Algebraic Signal Reconstruction via Polynomial Root Finding

19 concepts14 papers1 proposal

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.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_eigenstructure_based_parameter_estimatio_96b1d0af,
  title = {eigenstructure-based parameter estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/eigenstructure-based-parameter-estimation/rdr_96b1d0afebf14ee1abbb9d2f0a6565c1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_eigenstructure_based_parameter_estimatio_96b1d0af_v1,
  title = {eigenstructure-based parameter estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/eigenstructure-based-parameter-estimation/rdr_96b1d0afebf14ee1abbb9d2f0a6565c1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake