Algorithms and methods that reconstruct a polynomial (univariate or multivariate) assumed to have few nonzero terms from its evaluations by exploiting sparsity to reduce the number of samples and operations compared to dense interpolation.

Principle

Use the hypothesis that the target polynomial has a small support (few monomials) to transform evaluation data into a structured linear or nonlinear system (Prony-type, sparse resultant, compressed-sensing-inspired) that identifies monomial exponents and corresponding coefficients with far fewer probes than degree-based dense methods.

Demonstration

For a univariate polynomial with at most t nonzero terms and degree ≤ n, Prony/Borodin–Tiwari-style methods recover exponent positions and coefficients from O(t log n) carefully chosen evaluations, often by forming a Hankel/Toeplitz matrix and computing its nullspace or by solving a Vandermonde-like system; for multivariate polynomials one may use Kronecker substitution or multivariate sparse resultant techniques, acknowledging an increased combinatorial challenge and occasional need for randomization in variable reductions.

Misapplication

Assuming sparsity when the polynomial is not sparse leads to failed recovery or incorrect models; using too few samples relative to the true sparsity, or applying a sparse algorithm without accounting for noise or approximate coefficients, produces unstable or wrong reconstructions. Treating sparse interpolation as a black box without degree or support bounds invites ambiguity in results.

Consequence

Correct sparse interpolation dramatically lowers sample complexity and computational cost when sparsity holds, enabling recovery from far fewer evaluations and yielding interpretable compact representations; however the gains diminish or vanish when the sparsity assumption is violated or when noise/rounding errors are significant.

Reversal

Dense interpolation: ignore sparsity and use classical methods (Newton, Lagrange, multi-point evaluation or Gröbner-basis-based approaches) that require O(n) samples for degree-n polynomials and produce coefficients for every monomial up to the degree, trading parsimony for uniform stability and simplicity.

Boundary

Requires a valid sparsity model (known or bounded t), suitable evaluation points (avoiding degeneracies), and often exact arithmetic or a robust noise model; multivariate problems impose greater combinatorial complexity and may need variable projections or random shifts to avoid collisions of exponent vectors.

Semantic Tension

There is tension between sparse interpolation as an algebraic reconstruction problem and compressed sensing approaches from signal processing: both exploit sparsity but differ in the allowed coefficient domains, noise models, determinism vs probabilistic guarantees, and in the algebraic structure of monomial exponents versus generic sensing matrices.

Synthesis

Sparse interpolation is the class of reconstruction strategies that trade assumed model parsimony (few active monomials) for drastically lower sampling and computational cost by converting evaluations into structured algebraic systems whose solution reveals exponent support and coefficients, with success contingent on accurate sparsity bounds, suitable probes, and noise handling.