Source-linked AI summary
Full-Model Optimality for Tunable Linear Generative Priors in Compressed Sensing
Zhaoming Li, Paul Hand
TL;DR
The paper asks whether lower-complexity generative priors can improve compressed-sensing recovery in the simplest linear setting. It analyzes a nested family of SVD-related linear priors under noiseless Gaussian measurements and proves that the full-dimensional prior minimizes expected reconstruction error across the family. This baseline suggests that tunability gains seen with more general priors require mechanisms absent from the model studied here.
Problem
Prior work observed complexity-dependent reconstruction errors, but whether lower-complexity priors outperform the full prior in compressed sensing with linear generators was unresolved.
Method
The paper derives exact expected-error expressions for a nested family of linear generative priors formed by truncating the singular-value decomposition of an invertible full model.
Results
E(n) ≤ E(k) for every 1 ≤ k ≤ n, making the full-dimensional linear prior globally optimal in noiseless Gaussian compressed sensing.
Takeaways & Limitations
In this idealized setting, tuning to a lower-complexity linear prior does not improve expected reconstruction error, even when the signal distribution is effectively low-dimensional.
Takeaways & Limitations
The conclusions are limited to the noiseless linear Gaussian model and do not explain tunability effects that may arise from nonlinear generator geometry, noise, structured sensing, or reconstruction algorithms.
Abstract
from arXiv · showhide
Generative models have been studied experimentally and theoretically as priors for inverse problems such as compressed sensing. Recent work by Gunn et al. studied the use of generative priors with tunable complexity, where a family of generative priors with varying complexity is maintained and a specific complexity can be selected at inversion time. They demonstrated that lower reconstruction errors can be experimentally attained for a variety of inverse problems by appropriately tuning the complexity of the generative prior. In the present paper, we establish theory for compressed sensing in the setting of a tunable family of linear generative priors naturally related through their singular value decompositions. We prove that in noiseless Gaussian compressed sensing, the full-dimensional linear prior attains the minimum expected reconstruction error over the entire family of linear priors. Thus, in this idealized linear noiseless setting, tuning to a lower-complexity prior does not improve the expected reconstruction error. This result is in contract to the behavior of denoising, where lower complexity priors attain lower reconstruction errors due to a standard bias-variance tradeoff. This result indicates that the experimental benefits of tunability in compressed sensing with neural network priors arises due to nonlinearities in the generative models.
1 Introduction
Compressed sensing is ill-posed with few linear measurements, motivating structural and generative priors whose complexity can be selected at inversion time. This paper analyzes a nested linear family and finds that, in noiseless Gaussian compressed sensing, the full model minimizes expected reconstruction error across all complexities.
- Problem: Compressed sensing recovers an unknown signal from m ≪ n linear measurements, so additional structural assumptions are needed to overcome the problem's ill-posedness.Generative priors constrain recovery to the range of a model Gk mapping a k-dimensional latent variable into the signal space.
- Tunable priors: Tunable generative priors represent nested signal classes whose latent dimension can be selected at deployment after the measurement setting is known.Prior experiments reported a non-monotone, often U-shaped relationship between model complexity and reconstruction error.
- Main result: E(n) ≤ E(k) for every 1 ≤ k ≤ n, so the full generative model achieves the minimum expected reconstruction error throughout the tunable linear family.The result holds for every admissible decreasing singular-value spectrum, including spectra concentrated in a few dominant directions.
- Approach: The paper studies expected reconstruction error for noiseless compressed sensing using linear priors related by truncating the singular-value decomposition of an invertible full model.For each latent dimension k, the reconstruction signal and expected error E(k) are defined through the corresponding model and reconstruction rule.
- Main result: At k = m − 1 and k = m, expected reconstruction errors are infinite, while E(k) is finite and monotonically decreasing for k ∈ {m + 1, …, n}.The divergence arises from Gaussian matrices approaching singularity and producing nonintegrable inverse terms.
- Implications: Effective low-dimensionality alone does not create a tunability benefit: spectral truncation bias is not compensated by lower expected reconstruction error.The paper therefore identifies noiseless Gaussian compressed sensing with linear priors as a baseline where tunability does not improve fully averaged error.
2 Proof of the main theorem
The proof reduces the Gaussian compressed-sensing analysis to diagonal generators, then compares expected reconstruction errors across three latent-dimension regimes. These regime-specific results establish that the full model minimizes expected error throughout the nested linear family.
- Underdetermined regime: For m+1 ≤ k ≤ n, the proof derives an exact expected-error expression and shows E(k) decreases monotonically as k increases.The underdetermined regime is handled through monotonicity arguments based on projection identities and auxiliary lemmas.
- Reduction to diagonal generators: Rotational invariance of Gaussian measurements reduces the analysis to diagonal generators, so E(k) depends only on the singular values of the full generator.The proof first uses unitary invariance and equality in distribution of A and AU to justify the diagonal case.
- Global comparison: Combining all three regimes proves E(n) ≤ E(k) for every 1 ≤ k ≤ n and every admissible decreasing singular-value spectrum.The proof covers the full dimension range by treating the two boundary dimensions separately and showing the spectrum was arbitrary.
- Overdetermined regime: For 1 ≤ k ≤ m−2, a closed-form expression for E(k) yields E(n) ≤ E(k), so no strictly overdetermined reduced model beats the full model.The comparison follows from the derived error formula and the auxiliary term T(k)=k/(m−k−1), which increases with k.
Funding
The paper acknowledges PH’s support from two NSF awards.
- PH acknowledges support from NSF Awards DMS-1848087 and DMS-2022205.
- The acknowledged support comes from NSF Award DMS-1848087.
- The acknowledged support also comes from NSF Award DMS-2022205.
Data Availability
No experimental datasets were generated or analyzed; the reported numerical experiments use synthetically generated data from the manuscript’s models.
- No experimental datasets were generated in this study.
- No experimental datasets were analyzed in this study.
- The numerical experiments use synthetically generated data according to the manuscript’s models.
A MAP interpretation of the reconstruction rule
The paper derives the reconstruction rule from a MAP principle under a generative-model prior. In the noiseless compressed-sensing setting, the estimator is analyzed as the noise level tends to zero and expressed in latent coordinates.
- The estimator in (1.5) arises from a MAP principle applied to a k-dimensional generative model Gk.
- The MAP estimator uses the density induced by Gk and the ℓ2 norm, with γ denoting the noise level.
- In noiseless compressed sensing, the analysis takes γ ↓0 and distinguishes latent dimensions smaller or larger than the measurement count.
- In latent coordinates, the reconstruction is represented as ˆx(k) = Gkˆz(k).
- This latent-coordinate formulation yields the two-regime estimator stated in (1.5).
B Proofs of auxiliary results
The auxiliary proofs establish Gaussian identities, monotonicity arguments, projector bounds, and deterministic approximation bounds used in the paper’s analysis.
- Lemma 13 establishes an identity for a Gaussian vector x ∼N(0, In) and an arbitrary matrix M.
- The monotonicity proof reduces the behavior of H(k) to the monotonicity of h(Ak, t).
- Theorem 4 gives a deterministic approximation-error bound for a matrix A using its SVD, a test matrix Ω, and the sample matrix Y = AΩ.
- The projector proof flattens the top spectrum, enlarges the relevant range, and derives a semidefinite bound through block-matrix calculations.
- The proof bounds projector blocks using F⋆F, applies congruence and trace monotonicity, and concludes with the asserted bound.
C Wishart and Inverse Wishart Distributions
This appendix gathers the Wishart and Inverse Wishart definitions and facts used in the main text.
- The appendix collects basic definitions and facts about Wishart and Inverse Wishart distributions.These results support the paper’s main-text arguments.
- The listed results concern multivariate statistical distributions and their properties.
- Proofs of these results are available in standard multivariate-statistics references, including Muirhead (1982).
C.1 Wishart distribution
The Wishart distribution is defined from Gaussian observations and has key symmetry, positive-semidefiniteness, and invertibility properties.
- A matrix formed from n independent Gaussian rows with covariance Σ follows a Wishart distribution with n degrees of freedom and scale matrix Σ.
- Wishart matrices are almost surely symmetric positive semidefinite.
- When n ≥ p, Wishart matrices are almost surely invertible.
- For Σ = I_p, a Wishart matrix is the sample covariance matrix, up to a factor of n, for standard Gaussian data.
C.2 Inverse Wishart distribution
The Inverse Wishart distribution is defined as the inverse of a Wishart matrix and is used in Bayesian covariance modeling.
- An inverse Wishart random matrix S is defined as S = W^-1, where W is Wishart with scale matrix Ψ^-1 and n degrees of freedom.
- Its expectation is E[S] = Ψ / (n − p − 1).
- The Inverse Wishart distribution is commonly used as a conjugate prior for covariance matrices in Bayesian statistics.
C.3 Identities used in the paper
The paper repeatedly uses expectations for Wishart matrices, under a degrees-of-freedom condition, together with their concentration around nΣ.
- The identities in this subsection are used repeatedly in Sections 3.4.
- For W ∼ W_p(Σ, n) with n > p + 1, the subsection states useful expectation identities.
- The stated trace expectation identity is proportional to p Tr(Σ^-1) / (n − p − 1).
- The Wishart law concentrates around nΣ.
D Supplementary experiment result from Section 1.2
Figure 2 plots relative reconstruction error against latent dimension, revealing three theoretically predicted regimes across model dimensions.
- For k < m, reconstruction error follows a U-shaped pattern; at k = m, it reaches a sharp interpolation-threshold peak.
- For k > m, reconstruction error decreases monotonically, forming the third regime predicted by the theory.
- The plot shows relative reconstruction error versus latent dimension across the full range of model dimensions.The horizontal axis is latent dimension, and the vertical axis is relative reconstruction error.