Source-linked AI summary
Exact Reconstruction using Beurling Minimal Extrapolation
Yohann de Castro, Fabrice Gamboa
TL;DR
The paper asks whether finite-support measures can be uniquely reconstructed from finitely many non-adaptive generalized moments. It introduces generalized minimal extrapolation, connects its geometry to basis pursuit, and proves exact recovery results through interpolation. In particular, every nonnegative measure with support size s is recovered from 2s + 1 generalized moments, while the framework also yields deterministic sensing-matrix constructions.
Problem
The paper studies whether an unknown finite-support measure can be uniquely recovered from its first n + 1 generalized moments when both support and weights are unknown.
Method
Generalized minimal extrapolation recovers a target by minimizing total variation subject to matching generalized moments, using interpolation conditions to characterize exact recovery.
Results
2s + 1 generalized moments suffice to uniquely recover every nonnegative measure with support size s, and the program can recover it among finitely supported signed measures.
Takeaways & Limitations
The interpolation formulation extends basis-pursuit-style exact reconstruction to signed measures and supports a construction of deterministic sensing matrices for compressed sensing.
Takeaways & Limitations
The signed-measure recovery results assume finite support and, for the stated measure classes, structural conditions such as extrema Jordan type or Δ-spaced support.
Abstract
from arXiv · showhide
We show that measures with finite support on the real line are the unique solution to an algorithm, named generalized minimal extrapolation, involving only a finite number of generalized moments (which encompass the standard moments, the Laplace transform, the Stieltjes transformation, etc). Generalized minimal extrapolation shares related geometric properties with basis pursuit of Chen, Donoho and Saunders [CDS98]. Indeed we also extend some standard results of compressed sensing (the dual polynomial, the nullspace property) to the signed measure framework. We express exact reconstruction in terms of a simple interpolation problem. We prove that every nonnegative measure, supported by a set containing s points,can be exactly recovered from only 2s + 1 generalized moments. This result leads to a new construction of deterministic sensing matrices for compressed sensing.
Introduction
The paper extends exact sparse reconstruction from vectors to finite-support signed measures using generalized minimal extrapolation, based on finitely many generalized moments and total-variation minimization. It characterizes recovery through interpolation and identifies measure classes that can be recovered exactly, including nonnegative measures from 2s + 1 moments.
- Problem and framework: Generalized minimal extrapolation reconstructs finite-support signed measures from finitely many non-adaptive generalized moments.The generalized moments include frameworks such as standard moments, while the optimization searches over signed measures.
- Problem and framework: The program minimizes the total variation norm under generalized-moment constraints, paralleling basis pursuit’s ℓ1 minimization.For Fourier coefficients, generalized minimal extrapolation becomes Beurling Minimal Extrapolation.
- Exact recovery results: The recovery result is sharp in parameter count and remains valid when the optimization searches among all finitely supported signed measures.A support of size s has 2s parameters: s support locations and s weights.
- Interpolation characterization: Exact recovery is reduced to constructing bounded interpolating functions that equal prescribed signs on the positive and negative Jordan supports.For Δ-spaced supports, a polynomial can take values 1 and −1 on the two support sets while remaining bounded by 1.
- Recovery classes and sensing: The framework covers nonnegative, generalized Chebyshev, and Δ-spaced measures, and motivates deterministic sensing matrices for compressed sensing.For Δ-spaced measures, the required moment count is bounded in terms of Δ; the sensing construction uses evaluation vectors from a function family.
- Exact recovery results: 2s + 1 generalized moments suffice to uniquely recover every nonnegative measure with support size s.The theorem states that n ≥ 2s, corresponding to the first n + 1 generalized moments.
1. Generalized dual polynomials
Generalized dual polynomials turn exact reconstruction into an interpolation problem: under rank, interpolation, and strict off-support boundedness conditions, generalized minimal extrapolation uniquely recovers signed measures with prescribed support and signs.
- Sufficient recovery condition: A generalized dual polynomial provides a sufficient certificate for exact recovery of finite-support signed measures.Its existence is tied to an interpolation problem over the support and its complement.
- Sufficient recovery condition: If the generalized Vandermonde system has full column rank, the polynomial interpolates prescribed signs on the support, and |P(x)| < 1 off-support, recovery is unique.These are the three conditions in Lemma 1.1.
- Recovery scope: The interpolation result recovers every measure on a fixed support S with a fixed sign sequence, not only one choice of nonzero weights.Thus the certificate applies to the entire corresponding sign-structured family.
- Geometric interpretation: Generalized minimal extrapolation recovers all measures in a cone of measures sharing support-sign structure, which is linked geometrically to a face of the TV-unit ball.The cone is the conic span of an (s − 1)-dimensional face.
- Role of the conditions: Condition (i) supplies uniqueness, while conditions (ii) and (iii) constrain solutions to the relevant support-sign cone.Without the rank condition, the interpolation conditions alone need not identify a unique measure.
- Extrema Jordan type measures: For extrema Jordan type measures, the target is a solution, and full column rank of the associated Vandermonde system makes it the unique solution.This motivates the extrema Jordan type notion for exact reconstruction.
2. Exact reconstruction of the nonnegative measures
For homogeneous M-systems, generalized minimal extrapolation exactly recovers finitely supported nonnegative measures from a small number of generalized moments, and yields deterministic compressed-sensing matrices.
- Homogeneous M-systems: A homogeneous M-system is an M-system whose first function is constant, allowing constant generalized polynomials.Examples include real polynomials, trigonometric functions, characteristic-function families, Laplace transforms, and Stieltjes transformations.
- Exact reconstruction: 2s + 1 generalized moments suffice to uniquely recover every nonnegative measure supported on s points.The theorem requires n ≥ 2s, corresponding to observations K_n containing n + 1 generalized moments.
- Exact reconstruction: The recovery remains exact among all finitely supported signed measures, despite the target measure being nonnegative.The result uses only finitely many non-adaptive linear measurements and does not exploit nonnegativity in the optimization program.
- Nonnegative interpolation: A nonnegative generalized polynomial can vanish exactly on prescribed points when their index is at most the polynomial degree.This interpolation property supplies a key approximation-theoretic ingredient for the reconstruction theorem.
- Scope of the theorem: For non-homogeneous M-systems, counterexamples can invalidate the recovery theorem even when n ≥ 2s.The homogeneous assumption is therefore essential for the stated guarantee.
- Deterministic matrices: The construction produces deterministic sensing matrices for which basis pursuit exactly recovers all nonnegative s-sparse vectors when n ≥ 2s + 1.Unlike cited large-parameter deterministic results, the stated bound applies for all parameter values satisfying this inequality and does not depend on p.
3. Exact reconstruction for generalized Chebyshev measures
The section develops generalized Chebyshev polynomials and uses their extremal and equioscillation properties to identify signed measures exactly recoverable by GME from generalized moments.
- Generalized dual polynomials: M-systems provide dual polynomials whose boundedness and prescribed signs on Jordan supports imply exact GME recovery.The cosine system is an M-system, and its associated generalized polynomials can satisfy the required interpolation conditions.
- Classical examples: The cosine family can be mapped to Chebyshev polynomials, while complex exponentials yield corresponding trigonometric generalized moments.The cosine system (1, cos(πx), …, cos(nπx)) maps to (1, T1(x), …, Tn(x)); exponential moments are characteristic-function evaluations.
- Generalized Chebyshev polynomials: Generalized Chebyshev polynomials are uniquely characterized by degree, normalized supremum norm, and an alternating sequence of extrema.Their extremal property implies equioscillation, which supplies the sign structure used in reconstruction.
- Exact reconstruction: Chebyshev measures supported on the positive and negative alternation sets of T_k are uniquely recovered by GME from their first n + 1 generalized moments.The result applies when the Jordan support is included in (E+_Tk, E−_Tk) for some 1 ≤ k ≤ n.
- Exact reconstruction: For k = n, GME recovers signed measures supported on n alternation points from n + 1 generalized moments.This is a support-location-specific result; the section notes that the points are not sparse in the usual unconstrained sense.
4. The nullspace property for measures
The section extends the compressed-sensing nullspace property to generalized moment morphisms and studies interpolation conditions that guarantee exact measure reconstruction.
- Measure framework: The measure decomposition relative to a finite support separates its discrete component on the support from the component outside it.This decomposition underlies the measure-valued analogue of the vector nullspace property.
- Nullspace property: The generalized nullspace property is formulated for measures relative to a Jordan support family and is sufficient for unique GME recovery.The weak version guarantees that the target is a GME solution, while the full property guarantees uniqueness.
- Numerical experiments: The explicit spacing bound is not sharp, and the authors report that L2-minimizing polynomial experiments substantially lower the degree needed in practice.For support size 10 and spacings Δ = 1/15, 1/20, …, 1/55, the theoretical degree range is 1019–1059, whereas n = 80 suffices experimentally.
- Numerical experiments: Figure 2 measures the percentage of 100 random signed-measure realizations for which the fitted polynomial satisfies ∥P∥∞≤1 across spacing and degree values.White denotes 100% exact recovery and black denotes 0% in the experiments.
A.1. Proof of Lemma 1.1.
The appendix proves the dual-certificate lemma by combining total-variation subgradients, support localization, and injectivity of a generalized Vandermonde system.
- Support localization: The proof shows that any GME solution has support contained in the target support when the dual-certificate inequality is strict away from that support.The auxiliary lemma rules out nonzero mass outside the target support.
- Coefficient uniqueness: After support localization, the moment constraints reduce to a generalized Vandermonde system for the coefficient differences.Condition (i) makes this system injective, forcing the recovered coefficients to equal the target coefficients.
- Dual certificate: A generalized dual polynomial defines a total-variation subgradient that is fixed by the target signs on its support.The subgradient is perpendicular to feasible perturbations because the polynomial belongs to the generalized moment span.
Appendix B. Proofs of Section 2
The appendix identifies the dual-polynomial existence result used to prove exact recovery of nonnegative measures from generalized moments.
- Proof strategy: For a nonnegative measure supported on s points, the proof constructs a generalized dual polynomial before applying the reconstruction lemma.The resulting theorem states recovery when n is at least twice the support size.
B.1. Proof of Theorem 2.1.
The proof constructs a generalized dual polynomial interpolating 1 on the support, then uses the T-system structure and Vandermonde full rank to complete the recovery argument.
- Dual polynomial: A generalized polynomial P of degree d satisfies s ≤ d ≤ n, equals 1 at each support point, and has absolute value below 1 elsewhere.It is constructed as P = 1 − cQ, where Q is nonnegative and vanishes exactly on the support.
- Recovery argument: Lemma B.1 provides a generalized dual polynomial of degree at most n = 2s interpolating 1 on the s support points.The result is then combined with the full-column-rank property of the generalized Vandermonde system.
- Recovery argument: Because the family F is a T-system, the Vandermonde system has full column rank, enabling the proof to invoke Lemma 1.1.The construction uses a non-homogeneous M-system obtained from a positive, nonconstant function u0.
- Dual polynomial: The construction requires a homogeneous M-system so that the constant function 1 is itself a generalized polynomial.This assumption is explicitly described as essential.
B.3. Proof of Theorem 2.4.
The proof transfers generalized minimal extrapolation to finite-dimensional ℓ1 recovery through an isometric measure-to-vector map and then applies the nullspace property.
- Measure–vector correspondence: A bijective isometry ΘT maps vectors supported on T to finite measures supported on T, with the generalized Vandermonde matrix A representing the associated moments.The matrix is formed from evaluations of 1, u1, ..., un at the points of T.
- Measure–vector correspondence: An s-sparse vector x0 maps to a measure σ whose support has size at most s, so Theorem 2.1 makes σ the unique GME solution.The same uniqueness is then expressed as a measure optimization problem.
- ℓ1 recovery: The isometry transfers measure uniqueness to x0, which is therefore the unique solution of the ℓ1 program Ay = Ax0.This establishes the compressed-sensing formulation on the finite support set T.
- Nullspace property: If Kn satisfies the nullspace property, any GME solution σ⋆ must equal the target signed measure σ.The proof derives a contradiction because a nonzero nullspace perturbation would increase total variation.
C.1. Proof of Proposition 4.1.
The proof establishes uniqueness from the nullspace property by comparing total variation on the target support and its complement.
- Total-variation argument: The total variation of a perturbed measure decomposes into contributions on the support S and its complement S^c.The triangle inequality gives a lower bound involving the target variation, the support perturbation, and the off-support perturbation.
- Total-variation argument: A nonzero nullspace perturbation satisfies the nullspace-property inequality, forcing the candidate solution to have greater total variation than σ.This contradicts the minimization condition of GME, so the perturbation must vanish.
- Jordan support: The proof analyzes Jordan support by writing S = S+ ∪ S− and constructing Lagrange interpolation polynomials on its points.This sets up the interpolation-based certificate used for signed measures.
C.2. Proof of Lemma 4.2.
The proof builds a bounded generalized polynomial by interpolating suitably small Chebyshev extrema at the support points.
- Interpolation bound: The Lagrange interpolation basis is controlled in supremum norm by a bound L(∆) depending only on ∆.This bound determines how small the interpolated target values must be.
- Chebyshev construction: Chebyshev extrema ζi are chosen sufficiently small, then interpolated at the support points to construct P.The choice uses 2s extrema of a sufficiently high-degree first-order Chebyshev polynomial.
- Chebyshev construction: The resulting polynomial P has degree bounded by the prescribed limit and is used to certify the required interpolation behavior.The construction combines the Lagrange basis with the Chebyshev extrema.
Appendix D. Numerical Experiments
Numerical experiments compare target vectors with basis-pursuit solutions across three sparsity and moment settings, observing generally faithful reconstruction but some poorly estimated coefficients at s = 50 and n = 101.
- Figure 3 compares target vectors with basis-pursuit solutions for s = 10, 50, and 150, using n = 21, 101, and 301, respectively.All experiments use p = 500.
- Some coefficients are badly estimated when s = 50 and n = 101, possibly because this is the limit case n = 2s + 1.
- The experiments otherwise report faithful reconstruction when there are very few coefficients or a large number of moments.The cited examples are s = 10, n = 21 and s = 150, n = 301.