Sparse approximation and n-term rates

Let f belong to a Hilbert space with a complete orthonormal basis and square-summable coefficient sequence c. An N-term approximant uses at most N basis vectors, but the retained index set may depend on f. For a fixed set, orthogonal projection chooses the original coefficients on those indices and gives residual energy equal to the sum of the remaining squared magnitudes. No different retained coefficient values can do better on that same set.

To minimize over sets, exchange any retained smaller magnitude with an omitted larger one. The retained energy increases, so the residual decreases. Repeating this reasoning shows that N largest magnitudes are optimal, with ties handled arbitrarily. Write the sorted magnitudes in nonincreasing order to express the best error as a tail. Although each fixed-index projection is linear, selecting indices from the target is nonlinear: adding two signals can change which coordinates are largest.

Suppose the sorted magnitudes satisfy $c_k^*\le Ck^{-s}$ for every positive integer k, where s is strictly greater than one half. Square this bound and sum beyond N. Since the decreasing power tail is bounded by its integral from N to infinity, the squared error is at most $C^2N^{1-2s}/(2s-1)$. Taking a square root gives the displayed rate. The strict exponent condition is what makes that integral finite.

This is a sufficient bound on a particular coefficient class, with an explicit constant. It does not claim that every square-summable sequence has the same algebraic rate. At the borderline exponent one half, this argument gives no finite tail estimate, even though a specific sequence with extra logarithmic decay might still lie in the Hilbert space. The rate also belongs to the selected basis: a feature sparse in wavelets need not have the same sorted decay in global Fourier coordinates.

An adaptive approximation must specify retained locations as well as values. Counting N real coefficients alone therefore omits index storage, finite precision, and metadata such as scale or boundary conventions. Quantization changes each retained value and adds error. In an orthonormal basis, squared quantization errors on retained coordinates add independently to the omitted energy, giving a clean separation between selection and encoding. The optimal balance depends on the actual bit budget, not just the number of mathematical terms.

Finding large coefficients may require access to the full signal or a specialized recovery procedure. Compressed sensing asks a different question: can a sparse or compressible target be recovered from fewer measurements under conditions on the sensing map? A best N-term error is a benchmark for that task, not a proof that recovery succeeds. With nonorthogonal dictionaries, even the largest-coefficient selection rule can fail because atoms interact; sparse optimization then needs assumptions and algorithms beyond this elementary orthogonal argument.