# Near-Optimal and Tractable Estimation under Shift-Invariance

arXiv: https://arxiv.org/abs/2411.03383 · HTML: https://mlsanity.com/paper/2411.03383/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 38 references that are in the map.
- First posted on arXiv 5 Nov 2024.

## Builds on (most cited first, 6 of 6)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices](https://mlsanity.com/paper/1912.10754/) (2019)
- [Finite-sample analysis of M-estimators using self-concordance](https://mlsanity.com/paper/1810.06838/) (2018)
- [Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance](https://mlsanity.com/paper/1902.03046/) (2019)
- [Efficient First-Order Algorithms for Adaptive Signal Denoising](https://mlsanity.com/paper/1803.11262/) (2018)
- [Polytopal balls arising in optimization](https://mlsanity.com/paper/2011.05607/) (2020)

## Abstract (arXiv)

How hard is it to estimate a discrete-time signal (x1, ..., xn) ∈ mathbbCn satisfying an unknown linear recurrence relation of order s and observed in i.i.d. complex Gaussian noise? The class of all such signals is parametric but extremely rich: it contains all exponential polynomials over mathbbC with total degree s, including harmonic oscillations with s arbitrary frequencies. Geometrically, this class corresponds to the projection onto mathbbCn of the union of all shift-invariant subspaces of smashmathbbC^mathbbZ of dimension s. We show that the statistical complexity of this class, as measured by the squared minimax radius of the (1-δ)-confidence ℓ2-ball, is nearly the same as for the class of s-sparse signals, namely smashOleft(slog(en) + log(δ-1)right) · log2(es) · log(en/s). Moreover, the corresponding near-minimax estimator is tractable, and it can be used to build a test statistic with a near-minimax detection threshold in the associated detection problem. These statistical results rely upon a simple analytic observation: the interpretation of the Fourier coefficients of the Christoffel function of any shift-invariant subspace of smashmathbbC^mathbbZ as a reproducing filter with the smallest possible spectrum in all ℓp-norms, p ∈ [1,∞], at once.