arXiv CS open access

Full-Model Optimality for Tunable Linear Generative Priors in Compressed Sensing

2026 · arxiv_cs

arXiv CS · Papers · 2026

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Full-Model Optimality for Tunable Linear Generative Priors in Compressed Sensing

arXiv:2609.02790v1 [stat.ML] 2 Sep 2026

Zhaoming Li∗

Paul Hand†

Abstract 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.

Introduction

Compressed sensing concerns the recovery of an unknown signal x⋆ ∈ Rn from a limited number of linear measurements y = Ax⋆ + η, where A ∈ Rm×n is a measurement operator (e.g., a linear projection, convolutional blur, or other transformation)[19] with m ≪ n, and η ∈ Rm denotes measurement noise. A wide range of practical problems can be formulated as a recovery of an unknown signal from the noisy linear measurements, such as medical imaging[14, 23, 22], signal processing[16], and computational sensing[13] and singlepixel imaging. The above problem is ill-posed due to the compressive nature of the linear operator, meaning that there are infinitely many signals that fit the given measurements. Hence one needs additional assumptions to overcome the inherent ill-posedness. To enable successful recovery in such severely underdetermined settings, one must impose structural assumptions on the unknown signal x⋆ . Classical compressed sensing theory exploits lowdimensional structure, such as sparsity [3, 20, 4, 7] in a known basis or low-rank [9, 2, 17] structure for matrix recovery, to regularize the inverse problem. Although finding the sparsest solution to an underdetermined system of linear equations is NP-hard, convex relaxations such as ℓ1 minimization ∗

Department of Mathematics, Northeastern University, Boston, MA 02115, USA. Email: li.zhaom@northeastern.edu † Department of Mathematics and Khoury College of Computer Sciences, Northeastern University, Boston, MA 02115, USA.

can provably recover the true sparse signal x⋆ under suitable conditions on the measurement matrix, such as the Restricted Isometry Property or related Restricted Eigenvalue Condition. These models admit elegant theory and strong recovery guarantees. More recently, there has been a surge of interest in the use of generative models as signal structure prior in inverse problems. Motivated by the success of compressed sensing using generative models, a growing body of work studies recovery under the assumption that x⋆ lies in, or is wellapproximated by, the range of a generative model. In this framework, the compressed sensing problem can be viewed as finding x ∈ Rn such that y = Ax, subject to the constraint that x ∈ Range(Gk ), where Gk : Rk → Rn denotes a generative model that maps a low dimensional latent variable to a high dimensional signal. In practice, generative priors are typically employed through a two-stage workflow: 1. Training: A generative model is trained in an unsupervised learning on a representative dataset, independently of any specific downstream inverse problem; and 2. Inversion: At deployment time, an optimization problem is solved using the fixed, trained model to enforce consistency with the observed measurements. This isolation enables the use of rich, data-driven signal models that can be developed independently of the downstream inverse problem and reused across multiple measurement settings. A commonality of much of the existing literature is that the complexity of the generative model is fixed at training time. While the notion of complexity may vary across model classes, for example, being implicitly determined by the network architectural choices in GANs[1] or by the latent dimensionality in normalizing flows (NFs) [8], it cannot be adjusted once the model has been trained. As a result, once a generative model has been trained, its complexity is fixed and cannot be adapted to the inverse problem at hand. To address the issue of selecting model complexity at inversion time, recent work[11] has introduced generative priors with vary complexity, in which a single trained model implicitly represents a family of signal classes indexed by a complexity parameter. We refer to such a family as tunable because its latent dimension can be selected at inversion time. This tunable idea provides a different perspective on how generative priors can be deployed. Rather than committing to a single model complexity at training time, one can defer the choice of complexity until deployment, when the measurement operator, noise level, and sampling rate are fully specified. Empirical studies[11] demonstrate that reconstruction performance depends on this choice: as the model complexity varies, the reconstruction error often exhibits a non-monotone, U-shaped behavior that depends on factors such as the noise level and the number of measurements, with an intermediate complexity often yielding the best recovery.These observations suggest that it is worthwhile to train a tunable generative model in advance, so that its complexity can be selected for the specific inverse problem encountered at test time. Beyond empirical observations, recent work by Gunn et al. [11] provides theoretical insight into tunable generative priors in a simplified setting. Specifically, it analyzes the problem of denoising under additive Gaussian noise using a family of linear generative models indexed by a complexity parameter. In this setting, where the forward operator is the identity and all signal coordinates are observed, the expected reconstruction error can be computed explicitly as a function of the model complexity. The resulting characterization reveals a non-monotone, U-shaped dependence of the reconstruction error on the complexity parameter, reflecting a fundamental trade-off between underfitting the signal and overfitting the noise. In particular, the analysis shows that the optimal model complexity depends on the noise level, with higher noise favoring simpler models.

Our goal is to determine whether the benefits of tunability observed experimentally in compressed sensing with generative priors already arise in the simplest linear setting. This leads to a natural baseline question: can a lower-complexity prior outperform the full prior when the generator is linear and the target signal is itself drawn from the full model? The answer is not implied by the existing denoising theory. In denoising, the benefit of an intermediate model complexity is explained by a trade-off between underfitting the signal and overfitting the measurement noise. That mechanism is absent in the noiseless compressed sensing problem considered here. At the same time, because the measurement operator is underdetermined, one might expect that discarding weak spectral directions could improve reconstruction by restricting the feasible set. We show that this does not occur under the fully averaged risk over the Gaussian signal and measurement ensembles. For the tunable linear family {Gk }nk=1 obtained by truncating the singular-value decomposition of the full model Gn , the expected reconstruction error satisfies E(n) ≤ E(k), 1 ≤ k ≤ n. Thus, the full generative model attains the minimum expected reconstruction error throughout the family. This conclusion holds for every admissible decreasing singular-value spectrum, including spectra concentrated in a small number of dominant directions. Hence, even when the signal distribution is effectively low-dimensional, the bias introduced by spectral truncation is not compensated by an improvement in reconstruction error. Our result identifies noiseless Gaussian compressed sensing with linear generative priors as a baseline setting in which tunability does not improve the expected reconstruction error. In particular, linear spectral truncation alone cannot account for the gains observed experimentally with more general generative priors. The contrast suggests that such gains depend on mechanisms absent from the present model, such as nonlinear generator geometry, measurement noise, structured sensing operators, or properties of the reconstruction algorithm. An important direction for future work is to determine which of these mechanisms can rigorously produce a tunability effect, particularly for nonlinear generators such as ReLU networks, noisy compressed sensing, phase retrieval, and other nonlinear inverse problems.

1.1

Methodology

In this paper, we study tunable generative priors in the case of linear generative models. A generative model induces a probability distribution on the signal space by pushing forward a latent random variable. In the linear setting, this means that signals are generated according to x = Gz,

z ∼ N (0, I),

(1.1)

where G is a matrix, we say that G maps a latent variable to the ambient signal space. We fix an invertible matrix Gn ∈ Rn×n and write its singular value decomposition as Gn = U ΣV ⊤ ,

Σ = diag(σ1 , . . . , σn ),

σ1 ≥ · · · ≥ σn > 0,

(1.2)

where U, V ∈ Rn×n are orthogonal matrices. For each k ∈ [n], we define a k-dimensional generative model as follows. Let Gk := Uk Σk ∈ Rn×k ,

(1.3)

where Uk consists of the first k columns of U , and Σk = diag(σ1 , . . . , σk ). Each Gk induces a probability distribution by (1.1), which can be verified to be x ∼ N (0, Gk GkT ). The family {Gk }nk=1 is therefore a nested hierarchy of linear generative priors, ordered by model dimensionality. Observe that although Gn and Gn are different as matrices, they induce an identical 3

distribution for x. Note that the reduced model Gk captures the k directions of largest variance of the full Gaussian prior. We consider a compressed sensing problem in which the signal is sampled from the fulldimensional generative model, x⋆ = Gn z ⋆ ,

z ⋆ ∼ N (0, In ),

and the measurements are noiseless and Gaussian: y = Ax⋆ ,

A ∈ Rm×n ,

Aij ∼ N (0, 1),

m ≪ n.

(1.4)

 1 2   arg mink 2 ∥zk ∥2 subject to zk ∈R zb(k) = 1   arg min ∥AGk zk − y∥22 , zk ∈Rk 2

x b(k) = Gk zb(k),

y = AGk zk ,

k ≥ m, (1.5) k ≤ m.

The central quantity in this paper is the expected reconstruction error across the model complexities k: E(k) := EA Ex⋆ ∼Gn ∥x̂(k) − x⋆ ∥22 = EA Ez ⋆ ∼N (0,In ) ∥Gk ẑ(k) − Gn z ⋆ ∥22

(1.6)

We emphasize that the signal is sampled from the full-complexity model Gn , whereas reconstruction imaging is performed using a potentially lower-complexity prior Gk . This quantity captures how reconstruction quality varies with the chosen model dimension k, and in particular whether a generative prior of lower latent dimension can outperform the full prior.

1.2

Main results

Our main results concern the expected reconstruction error for noiseless compressed sensing under a nested family of linear generative models, as specified in (1.4). The main theorem shows that, in the noiseless linear setting, choosing a lower-dimensional model at inversion time cannot outperform the full model. Theorem 1 (Noiseless optimality of the full model). Fix an invertible matrix Gn ∈ Rn×n with singular value decomposition Gn = U ΣV ⊤ , Σ = diag(σ1 , . . . , σn ), σ1 ≥ · · · ≥ σn > 0, where U, V ∈ Rn×n are orthogonal. For each k ∈ [n], define the rank-k linear generative model Gk := Uk Σk ∈ Rn×k ,

Σk := diag(σ1 , . . . , σk ),

where Uk consists of the first k columns of U . Let A ∈ Rm×n have i.i.d. N (0, 1) entries, where 2 ≤ m ≤ n. Let z ⋆ ∼ N (0, In ) be independent of A, and define x⋆ := Gn z ⋆ ,

y := Ax⋆ .

For each k ∈ [n], let x b(k) be the reconstruction signal obtained from the model Gk according to the reconstruction rule (1.5), and let E(k) denote the expected reconstruction error defined in (1.6).2 Then E(n) ≤ E(k) for every k ∈ [n]. 1

When k = m, if AGk is invertible, the two optimization problems in (1.5) have the same unique solution zb(m) = (AGm )−1 y. For Gaussian A, AGk is full rank, this invertibility holds with probability one. 2 The quantity E(k) is interpreted as an extended-real-valued expectation. In particular, E(m−1) = E(m) = +∞; see Proposition 3.

Theorem 1 establishes that noiseless compressed sensing with linear generative priors does not exhibit a tunability effect. Specifically, if the underlying signal is sampled from an invertible linear model, then using any corresponding lower-rank linear model as a signal prior results in an expected reconstruction error no smaller than that obtained using the full model. This conclusion holds for every admissible decreasing singular value spectrum of the full-dimensional model. In particular, it applies even when the signal model is effectively low-dimensional. The proof of Theorem 1 is divided into three regimes according to the value of the latent dimension k relative to the measurement dimension m. For m + 1 ≤ k ≤ n, the latent reconstruction problem is underdetermined. In this regime, we derive an exact expression for the expected reconstruction error and show that E(k) is finite and monotone decreasing in k. For the two critical dimensions k = m−1 and k = m, the exact error formulas involve first inverse moments of Gaussian Gram matrices that are infinite. Consequently, E(m − 1) = E(m) = +∞. For 1 ≤ k ≤ m − 2, the reconstruction problem is strictly overdetermined. We derive an exact formula for E(k) and compare it with an upper bound for the full-model error E(n), obtaining E(k) ≥ E(n). Combining the conclusions from the three regimes shows that E(n) ≤ E(k) for every k ∈ [n], and proves Theorem 1. We first record the monotonicity result in the underdetermined regime. Theorem 2. Under the assumptions of Theorem 1, the expected reconstruction error E(k) is finite, and E(k) is monotone decreasing for every k ∈ {m + 1, . . . , n}. In the critical regime, the expected reconstruction error is infinite at both k = m−1 and k = m. This happens because the relevant Gaussian matrices can be arbitrarily close to singular, causing the inverse terms in the reconstruction error to have nonintegrable tails. Thus, although the estimators are well-defined almost surely, their expected reconstruction errors satisfy E(m−1) = E(m) = +∞. Proposition 3. Under the assumptions of Theorem 1, assume 2 ≤ m < n. Then the expected reconstruction error diverges: E(m − 1) = +∞,

E(m) = +∞.

Combining Theorem 2 with Proposition 3, we can rule out all model dimensions at and above the measurement threshold, except for the full model. Indeed, Proposition 3 gives E(m) = +∞, while Theorem 2 implies E(n) ≤ E(k) for every m + 1 ≤ k ≤ n. Therefore, E(n) ≤ E(k) for every m ≤ k ≤ n. No model dimension m ≤ k ≤ n can outperform the full model. Moreover, Proposition 3 also gives E(m − 1) = +∞, which rules out the endpoint k = m − 1 of the overdetermined regime. Hence the only lower-dimensional models that remain to be compared with the full model are 1 ≤ k ≤ m − 2. Our next result the strictly overdetermined regime 1 ≤ k ≤ m − 2. In this regiem, the reconstruction error admits an exact closed-form expression, which will later allow us to compare the lower-dimensional model with the full model. Lemma 1. Under the same model assumptions as Theorem 1, for every integer k ∈ {1, . . . , m − 2}, error of the MAP estimator using the model Gk satisfies E(k) =

k m−k−1

X n

σi2 ≥ E(n).

i=k+1

Lemma 1 gives an exact formula for E(k) when 1 ≤ k ≤ m − 2 and shows that E(k) ≥ E(n). Hence the full model is optimal throughout the strictly overdetermined regime. 5

Our analysis directly studies reconstruction error in expectation, rather than establishing a highprobability or asymptotic upper bound. This differs from much of the standard non-asymptotic compressed sensing literature, where recovery guarantees are often stated as deterministic consequences of conditions such as the restricted isometry property or null-space property [6, 10], together with high-probability results showing that random measurement matrices satisfy these conditions [6, 5, 10]. By contrast, in our linear generative setting we derive an exact decomposition of the expected reconstruction error under the Gaussian measurement ensemble. These expressions make the dependence of E(k) on the latent dimension explicit: for k < m, they give a closed-form formula, while for k ≥ m, they yield monotonicity of the risk. Combining the two regimes shows that the full prior Gn minimizes the expected reconstruction error over the entire tunable linear family. Hence the noiseless linear model serves as a baseline case in which tunability is available at the level of model selection, but does not improve the fully expected reconstruction error.

1.3

Experimental validation

We numerically illustrate Theorem 1 for several representative singular-value spectra. We set n = 100 and m = 20. By the diagonal reduction in Lemma 2, it suffices to take Gn = Σ = diag(σ1 , . . . , σn ). We consider the following five spectra: • Flat spectrum: 1 ≤ i ≤ n.

σi = 1, • Step spectrum:

• Power-law spectrum: • Exponential spectrum: • Linear spectrum:

( 1, σi = 0.1,

i ≤ k0 , i > k0 ,

σi = i−α , σi = e−β(i−1) ,

k0 = ⌊m/7⌋ = 2.

α = 2.

β = 0.1.

( 1, n = 1, σi = i−1 1 − ε n−1 , ε = 1, otherwise.

Rather than solving the reconstruction problem separately for each realization, we evaluate the expected reconstruction error using the analytical expressions derived above. For 1 ≤ k ≤ m − 2, we compute E(k) directly from (2.26). For m + 1 ≤ k ≤ n, we evaluate the expression in (2.6) and approximate its remaining expectation over the measurement matrix using T = 100 independent matrices A ∈ Rm×n with i.i.d. N (0, 1) entries. The expectation over the Gaussian latent variable has already been evaluated analytically in these formulas. The same samples of A are used to estimate E(n). We omit k = m − 1 and k = m, since E(m − 1) = E(m) = +∞. Figure 1 displays the singular-value spectra in the top row and the corresponding excess errors E(k) − E(n) in the bottom row, for k ∈ {1, . . . , m − 2} ∪ {m + 1, . . . , n}. A positive excess error means that the model Gk has larger expected reconstruction error than the full model Gn .

Figure 1: Singular-value spectra (top) and corresponding excess reconstruction errors E(k) − E(n) (bottom), with n = 100 and m = 20. The dimensions k = m − 1 and k = m, indicated by vertical dashed lines, are omitted because their expected reconstruction errors are infinite. Alt text: Two rows of plots showing five singular-value spectra (top) and the corresponding excess reconstruction errors E(k) − E(n) versus latent dimension k (bottom). Vertical dashed lines mark k = m − 1 and k = m. Across all five spectra, E(k) − E(n) is nonnegative, in agreement with Theorem 1. For some spectra, E(k) is non-monotone and may exhibit a U-shaped profile in the strictly overdetermined regime 1 ≤ k ≤ m−2. Nevertheless, these local minima remain above E(n). In the underdetermined regime m + 1 ≤ k ≤ n, the error decreases monotonically toward the full-model error. Thus, although E(k) can vary non-monotonically with the dimension over overdetermined regime, in all of the experiments reported above, the minimum reconstruction error is attained by the full model k = n.

1.4

Discussion

The results of this paper provide a complete characterization of the effect of model dimension in the noiseless linear Gaussian setting. For 1 ≤ k ≤ m − 2, the closed-form expression for E(k) yields the direct comparison E(k) ≥ E(n). At the two critical dimensions k = m − 1 and k = m, the expected reconstruction error diverges, while for k ≥ m + 1, E(k) is finite and monotonically decreasing. Combining these three regimes gives E(n) ≤ E(k), 1 ≤ k ≤ n. Thus, although the dependence of E(k) on the dimension may be locally non-monotone, the full model is globally optimal within the nested family of linear generative priors considered here. An important consequence is that effective low-dimensionality of the signal distribution is not, by itself, sufficient to produce a tunability benefit. The full-model optimality result holds for every admissible decreasing singular-value spectrum, including spectra in which most of the signal variance is concentrated in a small number of leading directions. Hence, even when the full model is effectively low-dimensional, truncating the weak spectral directions cannot reduce the fully averaged reconstruction error below that of the full prior. In this setting, the bias introduced by restricting the signal model is never compensated by a sufficient reduction in reconstruction error. These conclusions also clarify the scope of the linear theory. They show that tunability observed in more general inverse problems cannot be explained solely by spectral concentration or by the underdetermined nature of the measurement system. Rather, such behavior must arise from mechanisms that are absent from the present noiseless linear Gaussian model. In particular, a 7

tunability benefit may become possible when the generative model is nonlinear, when the measurement map is nonlinear, or when both forms of nonlinearity are present. Other departures from the present setting, including measurement noise or algorithm-dependent effects, may also alter the dependence of reconstruction error on model complexity. Determining which of these mechanisms is responsible for tunability, and how it interacts with the choice of latent dimension, remains an important direction for future work.

1.5

Organization of the paper

The remainder of the paper is organized as follows. Subsection 1.6 introduces the notation used throughout the paper. In Section 2, we present the architecture of the proof of Theorem 1. The proof is divided into three regimes. Section 2.3, we consider underdetermined regime m+1 ≤ k ≤ n, we prove that E(k) is monotone decreasing in k. In section 2.5, it is a strictly overdetermined regime 1 ≤ k ≤ m − 2, we derive a closed-form expression for E(k) and compare it with the full-model error. Finally, in Section 2.6 we consider the boundary dimensions k = m − 1 and k = m, we show that the expected reconstruction error diverges.

1.6

Notation

We introduce notation that will be used throughout the proofs of the monotonicity result for k ≥ m, Theorem 2, and the closed-form risk formula for k < m, Lemma 1. This notation is also used in the proof of Theorem 1, which combines the two regimes to show that the full model minimizes the expected reconstruction error over the entire tunable linear family. Let [n] = {1, . . . , n}. For fk as the last n − k columns of A. A ∈ Rm×n ,h k ∈ [n],i we will write Ak as the first k columns of A, A m fk . Let ai ∈ R be the i-th column of A. In the case of a diagonal Gk in Theorem Thus A = Ak , A Gk 0 f 2 we can write Gn = fk , where Gk = diag(σ1 , . . . , σk ), Gk = diag(σk+1 , . . . , σn ). For any 0 G −1 M ∈ Rn×k with k ≤ n, suppose M is full rank; let PM T = M T M M T M be the orthogonal projection on Range(M). Abusing notation, when we write (M1 − M2 )ii , it means (M1 )ii − (M2 )ii .

Proof of the main theorem

The proof of Theorem 1 has three components. First, we reduce the analysis to diagonal generators in Section 2.1. This reduction stated in Lemma 2, follows from the rotational invariance of the Gaussian measurement operator and shows that E(k) depends only on the singular values of Gn . Consequently, it suffices to study Gn = Σ = diag(σ1 , . . . , σn ). Second, we analyze the expected reconstruction error across the different model complexity regimes, and treating the two dimensions adjacent to the measurement threshold separately. In Section 2.3, for k ≥ m, we derive an exact decomposition that yields the monotonicity of E(k), this monotonicity result follows from an explicit analysis of the projection structure induced by the measurement operator. Hence the full model Gn minimizes the expected reconstruction error within the regime k ≥ m. In Section 2.5, for k < m, we derive the corresponding decomposition and find the closed formula of expected reconstruction error. This formula makes explicit how the reconstruction error depends on the latent dimension and the singular-value spectrum in the regime where the number of measurements exceeds the latent dimension. Finally, in Section 2.6, we complete the proof by handling the two remaining critical dimensions k = m − 1 and k = m, where the corresponding inverse Gaussian terms have non-integrable tails. 8

2.1

Reduction to diagonal generators

Lemma 2. Let Gn = U ΣV ⊤ and let Gk = Uk Σk . Under Gaussian measurements, the expected reconstruction error E(k) depends only on the singular values (σ1 , . . . , σn ). Consequently, it suffices to prove Theorem 1 in the diagonal case Gn = Σ = diag(σ1 , . . . , σn ). Proof of Lemma 2. Without loss of generality, it suffices to consider the case when Gn is diagonal, that is U = V = I. To see this, let Gn = U ΣV T and Gk = Uk Σk . First we define  1 2  arg min 2 ∥zk ∥2 s.t. y = AGk zk , for k ≥ m, k zk ∈R ẑ(k, A, Gk ) =  for k < m. arg min 12 ∥y − AGk zk ∥22 ,  zk ∈Rk

Observe that x̂(k) = Gk ẑ(k, A, Uk Σk ) = Uk Σk ẑ(k, A, Uk Σk ). The expected reconstruction error satisfies: E(k) := EA Ex⋆ ∼Gn ∥x̂(k) − x⋆ ∥22 = EA Ez ⋆ ∼N (0,In ) ∥Gk ẑ(k, A, Uk Σk ) − Gn z ⋆ ∥22 = EA Ez ⋆ ∥Uk Σk ẑ(k, A, Uk Σk ) − U Σz ⋆ ∥22 2 Σk = EA Ez ⋆ U ẑ(k, A, Uk Σk ) − U Σz ⋆ 0 2 2 Σk = EA Ez ⋆ ẑ(k, A, Uk Σk ) − Σz ⋆ , 0 2

(2.1)

where the second-to-last equation is given by the unitary invariance of the ℓ2 norm. It remains to show that E(k) does not depend on U. Observe ẑ(k, A, Uk Σk ) = ẑ(k, AU, Σ0k ). Thus, E(k) = EA Ez ⋆ = EA Ez ⋆ = EA Ez ⋆

2 Σk ẑ(k, A, Uk Σk ) − Σz ⋆ 0 2 2 Σk Σk ẑ(k, AU, ) − Σz ⋆ 0 0 2 2 Σk Σk ẑ(k, A, ) − Σz ⋆ . 0 0 2

where the last equality follows because A and AU are equal in distribution due to the rotational invariance of the Gaussian. This concludes the proof that without loss of generality, we can take U = V = I, which is the case of a diagonal Gn = diag(σ1 , . . . , σn ). By Theorem 2 in Section 1.2, E(k) decreases monotonically over m ≤ k ≤ n. By Lemma 1 in Section 1.2 , we show that there exist nok over 1 ≤ k ≤ m the reconstruction error E(k) beats the E(n).

2.2

Proof of Main Result

Proof of Theorem 1. Fix a spectrum σ1 ≥ · · · ≥ σn > 0. We prove that E(n) ≤ E(k) for every k ∈ {1, . . . , n} by splitting the range of k into three regimes around the measurement threshold m. 9

Let C(k) := 1 +

X k σi2 . m−k−1 i=k+1

Regime 1: m < k ≤ n. Here AGk ∈ Rm×k is wide, and by Theorem 2, E(k) is monotonic decreasing on {m, . . . , n}. Hence its minimum over this range is attained at the right endpoint k = n, so E(k) ≥ E(n) for all m < k ≤ n. Regime 2: 1 ≤ k ≤ m − 2. n

X k E(k) = C(k) = 1 + σi2 . m−k−1

i=k+1

Moreover, by Lemma 1, it provides a bound on the full-model error for every admissible internal rank k satisfying m − k ≥ 2, E(n) ≤

X k σi2 = C(k). m−k−1 i=k+1

Combining the two displays gives E(n) ≤ C(k) = E(k) for all 1 ≤ k ≤ m − 2. Regime 3: k ∈ {m − 1, m}. These two boundary dimensions are handled by Proposition 3, which states that E(m − 1) = +∞, E(m) = +∞. Since E(n) is finite by Theorem 2, we immediately obtain E(n) ≤ E(k),

k ∈ m − 1, m.

The three regimes 1 ≤ k ≤ m − 2, k ∈ {m − 1, m}, m + 1 ≤ k ≤ n exhaust {1, . . . , n}, and in each regime we obtained E(n) ≤ E(k). Since the spectrum was arbitrary, the inequality holds for every strictly decreasing admissible spectrum, which completes the proof.

2.3

Main Result for Underdetermined System

Recall without loss of generality, we have assumed that Gn = diag(σ1 , . . . , σn ), then Gn = Gn . In this case Gk = G0k ∈ Rn×k where Gk = diag(σ1 , . . . , σk ). For k ≥ m, x̂(k) = Gk ẑ(k) ẑ(k) = arg min zk ∈Rk

1 ∥zk ∥22 2

s.t.

y = AGk zk .

(2.2)

Lemma 3. Suppose x⋆ ∼ Gn , Gn = diag(σ1 , . . . , σn ) has singular values σ1 ≥ σ2 ≥ · · · ≥ σn > 0. i.i.d

Let Gk = diag(σ1 , . . . , σk ). Let A ∈ Rm×n , Aij ∼ N (0, 1). For fixed A, for k ∈ [m, n], and the MAP estimator from (2.2) obeys 2

Ex⋆ ∼Gn x̂(k) − x⋆ 2 = Gk PGT AT − Gk k

furthermore, 2

E(k) = EA Ex⋆ ∼Gn x̂(k) − x⋆ 2 10

2 F

e k 2 + Gk (Ak Gk )† A ek G ek + G F

2 F

= EAk

∥Gn ∥2F −

G2k , PGT AT k k

†

+ Gk (Ak Gk )

n X

2 F

! σi2

i=k+1

where PGT AT = GTk ATk (Ak Gk GTk ATk )−1 Ak Gk . k

Proof of Lemma 3. By (2.2), the constraint that y = AGk ẑ(k). We write z ⋆ =

zk⋆ , where zk⋆ ∈ zek⋆

Rk , zek⋆ ∈ Rn−k . As AGk = Ak Gk has rank m with probability 1, the solution to (2.2) is ẑ(k) = (Ak Gk )† AGn z ⋆ , where (Ak Gk )† = GTk ATk (Ak Gk GTk ATk )−1 . The expected reconstruction error satisfies: Ex⋆ ∼Gn ∥x̂(k) − x⋆ ∥22 = Ez ⋆ ∼N (0,I) ∥Gk ẑ(k) − Gn z ⋆ ∥22 2 Gk = Ez ⋆ ẑ(k) − Gn z ⋆ 0 2 2 Gk 0 Gk ⋆ ẑ(k) − = Ez ⋆ fk z 0 0 G 2 2 ⋆ Gk z Gk ẑ(k) = Ez ⋆ − f ek⋆ 0 Gk zk 2 fk ze⋆ = Ez ⋆ ∥Gk ẑ(k) − Gk zk⋆ ∥22 + Ez ⋆ G k = Ez ⋆ Gk (Ak Gk )† AGn z ⋆ − Gk zk⋆

2 2

fk ∥2F + ∥G

(2.3)

fk ze⋆ ) − Gk z ⋆ fk G = Ez ⋆ Gk (Ak Gk )† (Ak Gk zk⋆ + A k k

2 2

fk ∥2 + ∥G F

fk ze⋆ fk G = Ez ⋆ (Gk (Ak Gk )† Ak − Ik )Gk zk⋆ + Gk (Ak Gk )† A k

2 2

fk ∥2 + ∥G F

= Ez ⋆ (Gk (Ak Gk )† Ak − Ik )Gk zk⋆ 2 E D † fk ze⋆ fk G + 2Ez ⋆ Gk (Ak Gk ) Ak − Ik Gk zk⋆ , Gk (Ak Gk )† A k fk ze⋆ fk G + Ez ⋆ Gk (Ak Gk )† A k = Gk (Ak Gk )† Ak Gk − Gk = Gk PGT AT − Gk k

2 F

2 2

fk ∥2 + ∥G F

fk fk G + Gk (Ak Gk )† A

2 F

fk G fk fk 2 + Gk (Ak Gk )† A + G F

fk ∥2 + ∥G F

(2.4)

2 F

(2.5)

(2.3) follows by Lemma 13, and (2.4) follows by Lemma 13 and the fact that zk⋆ , and zek⋆ are independent with zero mean. By Lemma 4, we get: D E 2 ek G ek E(k) = ∥Gn ∥2F − EA G2k , PGT AT + EA Gk (Ak Gk )† A k

= ∥Gn ∥2F − EAk G2k , PGT AT k

+ EAk Gk (Ak Gk )†

2 F

n X

σi2 .

(2.6)

i=k+1

We now return to the proof of Theorem 2. After deriving the exact expression for E(k) in the regime k ≥ m, we verify that this expression is monotone decreasing in the selected latent dimension k. 11

Proof of Theorem 2. For fixed A, let Rk := Ex⋆ ∼Gn x̂(k) − x⋆ 2 , where x̂(k) is given by (2.3). By definition, E(k) = EA Rk . Thus, for m < k ≤ n, R − R . E(k) − E(k − 1) = EA Rk − EA Rk−1 = EA Rk − Rk−1 = EAk−1 EA k k−1 ^ k−1

In order to show E(k) − E(k − 1) ≤ 0, we will show that for all full rank Ak−1 , EA ^ Rk − Rk−1 ≤ 0.

(2.7)

k−1

f ] Since A k−1 = [ak , Ak ], let fk := EA f Rk . Therefore, we have k

EA f Rk − Rk−1 ^ Rk − Rk−1 = Eak EA

(2.8)

k−1

Eak (fk ) − fk−1 = Eak (fk − fk−1 ). Hence, for full rank fixed Ak−1 , it suffices to show that , Eak (fk − fk−1 ) ≤ 0.

(2.9)

The remainder of this proof establishes (2.9). By Lemma 3, fk is given by fk =

2 Gn F −

G2k , PGT AT k k

+ G k Ak G k

n † 2 X F

σi2 =

2 Gn F − T1 (k) + T2 (k)

σi2 ,

i=k+1

where T1 (k) = G2k , PGT AT , T2 (k) = Gk Ak Gk k k Thus,

n X

† 2 F

n X fk − fk−1 = T1 (k − 1) − T1 (k) − T2 (k − 1)σk2 + T2 (k) − T2 (k − 1) σi2 .

(2.10)

i=k+1

i h Define Mk = Ak Gk = Mk−1 , mk . By Lemma 4, we know k−1 X

T1 (k) − T1 (k − 1) =

σi2 − σk2 PGT AT − PGT k

T k−1 Ak−1

= ii

i=1

k−1 X

σi2 − σk2 PM T − PM T ii k

k−1

i=1

By Lemma 5, we know T2 (k)−T2 (k−1) =

k−1 X

σi2 −σk2

T T † Mk† Mk † −Mk−1 Mk−1 †

i=1

+σk2

T Mk† Mk†

−Tr

† † T Mk−1 Mk−1

By (2.24) we induce T2 (k − 1), plug T1 (k − 1) − T1 (k), T2 (k) − T2 (k − 1), and T2 (k − 1)’s expressions into the equation (2.10), we get fk − fk−1 = −

k−1 X

σi2 − σk2

PM T − PM T k

k−1

i=1

−

k−1 X

T 2 † σi2 Mk−1 Mk−1 † σk

i=1 k−1 X

σi2 − σk2

Mk† Mk †

† − Mk−1 Mk−1 †

i=1

+ σk2 Tr Mk† Mk

† T

† − Tr Mk−1 Mk−1

n X

† T

σi2

i=k+1

X n

σi2 .

(2.11)

i=k+1

By Lemma 8 we know the upper bound for the last two terms is 0. The first term upper bound is: −

k−1 X

σi2 − σk2

PM T − P M T k

k−1

i=1

=−

≤−

k−1 X

k−1 X + σi2 PM T − PM T σk2 PM T − PM T k

i=1 k−1 X

k−1

i=1

, σi2 PM T − PM T k

k−1

i=1

where the inequality follows from Lemma 5. Therefore, fk − fk−1 ≤ −

k−1 X

k−1 X T † σi2 PM T − PM T − σk2 σi2 Mk−1 Mk−1 † k

k−1

i=1

From Lemma 9 we know that, −

k−1 X

k−1 −1 −1 X T T T Mk−1 , mk mTk Mk−1 Mk−1 Mk−1 Mk−1 σi2 PM T − PM T ≤ σi2 Mk−1 k

k−1

i=1

Observe that, k−1 X

σi2

T † Mk−1 Mk−1 †

i=1

σk2 = =

k−1 X i=1 k−1 X

σi2

−2 T T Mk−1 σk2 Mk−1 Mk−1 Mk−1 ii

−1 −1 2 T T T 2 σi Mk−1 Mk−1 Mk−1 Mk−1 . Im σk Mk−1 Mk−1 ii

i=1

Therefore, we have fk − fk−1 ≤

k−1 X

σi2

T Mk−1

T Mk−1 Mk−1

−1

mk mTk − Im σk2

T Mk−1 Mk−1

−1

Mk−1

(2.12)

i=1

In order to establish (2.10), we take the expectation of (2.12) with respect to ak , and using mk = σk ak , and ak ∼ N (0, Im ). Following the isotropy property Eak (mk mTk ) = σk2 Im . We obtain " k−1 # −1 −1 X 2 T T T 2 T Eak (fk − fk−1 ) ≤ Eak σi Mk−1 Mk−1 Mk−1 mk mk − Im σk Mk−1 Mk−1 Mk−1 ii

i=1

k−1 −1 −1 X T 2 T 2 T T Eak mk mk − Im σk Mk−1 Mk−1 Mk−1 = σi Mk−1 Mk−1 Mk−1 ii

i=1

(2.13) = 0. 13

2.4

Auxiliary Lemmas for the Underdetermined Regime

The proof of monotonicity in the regime k ≥ m relies on several projection identities. We collect these auxiliary lemmas here. Gk 0 m×n , Lemma 4. Let Gn = diag(σ1 , . . . , σn ) = fk , where σi is decreasing. Let A ∈ R 0 G i.i.d

Aij ∼ N (0, 1). Then the following expectation identities hold: EA Gk PM T − Gk k

2 F

fk ∥2F = Gn 2 − EA G2 , P T . + ∥G k M k F k

EA Gk (Mk )† Mk

2 F

= EAk Gk (Mk )†

2 F

n X

σi2 .

(2.14)

(2.15)

i=k+1

Proof of Lemma 4. First, we show (2.14) 2 2 fk 2 fk 2 = EA Gk P T − Gk + G EA Gk PM T − Gk + G Mk F F k F F D E 2 f = EA Gk PM T − Gk , Gk PM T − Gk + Gk F k k E D 2 2 2 f = EA Gk PM T F − 2 Gk PM T , Gk + Gk F + Gk F k k E D 2 2 2 T T f = EA Gk PM T F − 2 Gk PM T PM T Gk , I + Gk F + Gk F k

(2.16)

2 fk 2 + Gk F + G F 2 2 2 fk 2 = EA Gk PM T F − 2 Gk PM T F + Gk F + G F k k 2 2 fk 2 = EA − Gk PM T F + Gk F + G F k D E 2 = EA Gn F − G2k , PM T k D E 2 = Gn F − EAk G2k , PM T

= EA

Gk P M T k

2 −2 F

Gk PM T , Gk PM T k

D E 2 where (2.16) follows by P 2 = P , and P T = P . The last equality holds because Gn F − G2k , PM T k fk . is independent of A Next, we want to show (2.15), 2 2 † † fk fk = EAk EAf Gk Mk M EA Gk Mk M k F F D † † E fk f = EAk EAf Gk Mk Mk , Gk Mk M k † T † T f f = EAk Gk Mk Gk Mk , EAf Mk Mk k

= EAk = EAk

G k Mk G k Mk

† T † T

n † X 2 T G k Mk , σi Eai ai ai † G k Mk ,

i=k+1 n X

σi2 I

(2.17)

(2.18)

i=k+1

= EAk

G k Mk

T †

†

G k Mk , I

X n

σi2

i=k+1

= EAk Gk Mk

† 2 F

n X

σi2 .

i=k+1

Here, by the independence of columns of A, we can induce (2.17) to (2.18). m×k has full rank, m ∈ Rm , Lemma 5. Let Mk = Mk−1 , mk be a matrix ∈ Rm×k k , where Mk ∈ R and k > m. ∀i ∈ [k − 1], we have PM T ii ≤ PM T ii . k

k−1

Proof of Lemma 5. Since it MkT has full column rank, we can express this projector explicitly as −1 Mk PM T = MkT Mk MkT k T !−1 Mk−1 Mk−1 , mk Mk = MkT mTk −1 T Mk + mk mTk = MkT Mk−1 Mk−1 Evaluating the (i, i) entry, where i ∈ [k − 1], let e′i ∈ Rk−1 , ei ∈ Rk . PM T ii = eTi PM T ei k k −1 T T T = ei Mk Mk−1 Mk−1 + mk mTk Mk ei T −1 Mk−1 T Mk−1 0 ei = eTi Mk−1 Mk−1 + mk mTk 0 −1 T T Mk−1 Mk−1 Mk−1 e′i ≤ (e′i )T Mk−1 = PM T ii k−1

T T , so The inequality follows from Mk−1 Mk−1 + mk mTk ⪰ Mk−1 Mk−1 −1 T . Mk−1 Mk−1

T Mk−1 Mk−1 + mk mTk

−1

⪯

We now use the above lemma to prove the following lemma. Lemma 6. Under the same assumptions as Lemma 3, for fixed m ∈ [1, n], k ∈ [m + 1, n], let T1 (k) = G2k , PGT AT = G2k , PM T , k

T1 (k) − T1 (k − 1) =

k−1 X

σi2 − σk2 PM T − PM T ii ≤ 0 k

i=1

and T1 (k) is decreasing monotonically. 15

k−1

(2.19)

Proof of Lemma 6. Observe that, T1 (k) = G2k , PM T k

k−1 X

σi2 PM T ii + σk2 PM T kk k

i=1 k−1 X

σi2 PM T

k−1

+ PM T − PM T

k−1 ii

+ σk2 PM T kk k

i=1

= T1 (k − 1) +

k−1 X

σi2 PM T − PM T

+ σk2 PM T kk

k−1

+ σk2 PM T kk

i=1

Noting that Tr(PM T ) = k

i=1 (PMkT )ii = m,

T1 (k) − T1 (k − 1) =

k−1 X

σi2 PM T − PM T k

i=1 k−1 X i=1 k−1 X

k−1

m−

k−1 X

PM T ii k

i=1

σi2 PM T − PM T

k−1

σi2 PM T − PM T

+ σk2 ii

k−1

i=1 k−1 X

σi2 PM T − PM T ii + σk2 k k−1

i=1 k−1 X

− σk2

k−1 X

PM T

k−1

i=1 k−1 X

− ii

k−1 X

PM T ii k

i=1

PM T − P M T k

k−1

i=1

PM T − P M T k

k−1

σ 2 − σk2 ii i

i=1

≤0 Pk−1 i=1 (PMkT )ii + (PMkT )kk = m. i=1 (PMkT )ii = Pk−1 The third equality follows Tr(PM T ) = i=1 PM T ii = m. k−1 k−1

The second equality follows Tr(PM T ) =

Lemma 7. Let Mk = Mk−1 , mk ∈ Rm×k be a matrix ∈ Rm×k , where Mk−1 ∈ Rm×(k−1) has full rank, mk ∈ Rm and k ≥ m. † Tr Mk−1 (Mk−1 † )T ≥ Tr Mk† (Mk † )T (2.20) and

† Mk−1 (Mk−1 † )T

≥ Mk† (Mk † )T

∀i ∈ [k − 1]. Proof of Lemma 7. −1 Mk† = MkT Mk MkT T −1 Mk−1 T T M M + m m , = k−1 k−1 k k mTk 16

(2.21)

T , m mT all PSD matrix. here Mk−1 Mk−1 k k

T −1 −1 Mk−1 T T T T Mk−1 mk M M + m m M M + m m k−1 k−1 k k k−1 k−1 k k T mk T −2 Mk−1 T T Mk−1 mk = M M + m m k−1 k k−1 k T mk T −2 Mk−1 T Mk−1 mk ≼ Mk−1 Mk−1 T mk T T )−2 M T T −2 Mk−1 (Mk−1 Mk−1 k−1 Mk−1 (Mk−1 Mk−1 ) mk = T )−2 M T )−2 m mTk (Mk−1 Mk−1 mTk (Mk−1 Mk−1 k−1 k

Mk† (Mk † )T =

† We are using trace to investigate the behavior of Mk† (Mk † )T and Mk−1 (Mk−1 † )T on both sides. −2 T † T T † Tr Mk−1 Mk−1 Mk−1 = Tr Mk−1 Mk−1 Mk−1 −1 −1 T T T Mk−1 Mk−1 Mk−1 = I, Mk−1 Mk−1 Mk−1 −2 T T = Mk−1 Mk−1 , Mk−1 Mk−1 −1 T = I, Mk−1 Mk−1 −2 −2 † T T T T T † T T mk Mk−1 + mk Mk−1 Mk−1 + mk mk Tr Mk Mk = Tr Mk−1 Mk−1 Mk−1 + mk mk −2 −2 T T T + mk mTk mk Mk−1 + I, mTk Mk−1 Mk−1 + mk mTk Mk−1 Mk−1 = I, Mk−1 −2 −2 T T T T T T + mk mk , Mk−1 Mk−1 + mk mk = Mk−1 Mk−1 , Mk−1 Mk−1 + mk mk −2 T T + mk mTk Mk−1 + mTk mk , Mk−1 Mk−1 = Mk−1 −1 T T = I, Mk−1 Mk−1 + mk mk

−1 −1 † T +m mT T † T ≥ Tr M † M † T . , we proved Tr M Since Mk−1 Mk−1 ≼ M M M k k k−1 k−1 k−1 k k−1 k For entry-wise perspective, we have: −2 † † T T T T T Mk M k = ei ei , Mk Mk−1 Mk−1 + mk mk Mk ii −2 T T T T = Mk ei ei Mk , Mk−1 Mk−1 + mk mk Since i ∈ [k − 1], So we can use Mk−1 substitute Mk . −2 T T T T = Mk−1 ei ei Mk−1 , Mk−1 Mk−1 + mk mk −2 T T T T = ei ei , Mk−1 Mk−1 Mk−1 + mk mk Mk−1 17

−2 T T ei eTi , Mk−1 Mk−1 Mk−1 Mk−1 T † † = Mk−1 Mk−1 ≤

which proves the following Lemma. Lemma 8. Under Lemma 3 assumptions, let T2 (k) = Gk (Ak Gk )†

T2 (k) − T2 (k − 1) =

k−1 X

(σi2 − σk2 )

T T † Mk† Mk † − Mk−1 Mk−1 †

i=1

2 F

. For all m ≤ k,

+ σk2

T T † Tr Mk† Mk † − Tr Mk−1 Mk−1 †

≤0

(2.22)

and as a consequence, Gk (Ak Gk )†

2 F

n X

σi2

(2.23)

i=k+1

is monotonically decreasing. Pn

2 i=k+1 σi decreases as k increases. Therefore, to establish the 2 desired result, it is sufficient to show that Gk (Ak Gk )† is a decreasing function of k. Thus, we F

Proof of Lemma 8. Observe that

want to show: −2 −2 † T 2 T T T 2 †T 2 mk + mk mTk Mk−1 + σk mTk Mk−1 Mk−1 ≥ Gk−1 , Mk−1 Mk−1 Mk−1 + mk mk Gk−1 , Mk−1 Mk−1 Recall Mk† = Ak Gk

†

∈ Rk×m

T2 (k) = Gk Ak Gk

† 2 F

D T E † TE D 2 = Gk , Mk† Mk † = G2k , Ak Gk Ak Gk †

D T E T2 (k) = G2k , Mk† Mk † =

k X i=1 k−1 X i=1 k−1 X

T σi2 Mk† Mk † σi2

T Mk† Mk †

(2.24)

+ σk2

T Mk† Mk †

T T T T † † Mk−1 † + σk2 Mk† Mk † σi2 Mk−1 Mk−1 † + Mk† Mk † − Mk−1 ii

i=1

= T2 (k − 1) +

k−1 X

T T T † Mk−1 † + σk2 Mk† Mk † σi2 Mk† Mk † − Mk−1 ii

i=1

T2 (k) − T2 (k − 1) =

k−1 X

T T T † σi2 Mk† Mk † − Mk−1 Mk−1 † + σk2 Mk† Mk † ii

i=1

k−1 X

T T † σi2 Mk† Mk † − Mk−1 Mk−1 †

i=1

+ σk2

Mk† Mk †

k−1 X

−

T kk

k−1 X

† Mk−1 Mk−1 †

k−1 X

T T † Mk−1 Mk−1 † − Mk† Mk †

σi2 − σk2

− Mk† Mk †

Mk† Mk †

k−1 X

Mk† (Mk † )T

σi2 − σk2

−

† − Mk−1 Mk−1 †

T ii

k−1 X

† Mk−1 (Mk−1 † )T − Mk† (Mk † )T

+ σk2

Mk† Mk †

T Mk† Mk †

i=1

† − Mk−1 Mk−1 †

− Tr

≤

T ii

i=1

+ σk2

i=1

T † Mk−1 Mk−1 †

Based on Lemma 7, we have k−1 X

Mk† (Mk † )T

i=1

k−1 X

† (Mk−1 † )T Mk−1

i=1

† (Mk−1 † )T Tr Mk† (Mk † )T ≤ Tr Mk−1 T2 (k) − T2 (k − 1) ≤ 0. Lemma 9. Under Lemma 3 assumption, let Mk = Ak Gk be a sequence of matrices evolving as Mk = [Mk−1 , mk ], where mk = σk ak is an additional column vector. The projection matrices associated with these matrices are given by: PGT AT = PM T = MkT (Mk MkT )−1 Mk , k

PGT

T k−1 Ak−1

= PM T

k−1

T T )−1 Mk−1 . (Mk−1 Mk−1 = Mk−1

Then, k−1 X

k−1 −1 −1 X T T T σi2 PM T − PM T ≥− σi2 Mk−1 Mk−1 Mk−1 mk mTk Mk−1 Mk−1 Mk−1 . k

k−1

i=1

(2.25) Proof of Lemma 9. Since k−1 X i=1

σi2

PG T AT − P G T k

T k−1 Ak−1

k−1 X i=1 k−1 X

σi2 σi2

MkT

Mk MkT

T Mk−1

−1

Mk MkT

i=1

−1

−

Mk−1

T Mk−1

−

T Mk−1 Mk−1

T Mk−1

−1

Mk−1

T Mk−1 Mk−1

−1

Mk−1

k−1 X

σi2

−1 −1 T T T Mk−1 − Mk−1 Mk−1 Mk−1 Mk Mk ii

i=1

−1 −1 T We know that Mk MkT = Mk−1 Mk−1 + mk mTk , By Lemma 16, we know that: −1 −1 −1 −1 T T T T ≽0 mk mTk Mk−1 Mk−1 + Mk−1 Mk−1 − Mk−1 Mk−1 Mk−1 Mk−1 + mk mTk Therefore, k−1 X i=1

σi2

PG T AT − P G T k

T k−1 Ak−1

k−1 X

i=1 k−1 X

σi2

−1 −1 T T T Mk−1 Mk−1 Mk Mk − Mk−1 Mk−1 ii

−1 −1 2 T T T T σi Mk−1 Mk−1 Mk−1 + mk mk − Mk−1 Mk−1 Mk−1

i=1 k−1 X

≥−

−1 −1 T T T Mk−1 mk mTk Mk−1 Mk−1 Mk−1 Mk−1 σi2 Mk−1

. ii

i=1

2.5

Main Result for Overdetermined System

We now consider the overdetermined regime 1 ≤ k ≤ m. Our goal in this section is to derive an explicit expression for E(k) and use it to compare E(k) with the full-model error E(n). For k ≤ m, we know that ẑ(k) = arg min 21 ∥AGk zk − y∥22 . Since Ak Gk has full column rank with zk ∈Rk

† probability 1, solving this least-squares problem gives ẑ(k) = Ak Gk AGn z ⋆ , where ẑ(k) ∈ Rk , −1 † GTk ATk . Here Ak ∈ Rm×k , Gk ∈ Rk×k . Ak Gk = GTk ATk Ak Gk Lemma 10. Suppose x⋆ ∼ Gn , Gn = diag(σ1 , . . . , σn ) ∈ Rn×n , such that σ1 ≥ σ2 ≥ · · · ≥ σn > 0. For any k ≤ m ≤ n, the random matrix A ∈ Rm×n with i.i.d. N (0, 1) entries, the MAP estimator obeys w w2 E(k) = EA Ex⋆ ∼Gn wx̂(k) − x⋆ w2 n n w X † w w w2 X 2 = σi2 + EAk wGk Ak Gk w σi (2.26) F

i=k+1

Proof of Lemma 10. w w2 E(k) := EA Ex⋆ ∼Gn wx̂(k) − x⋆ w2 w w2 w w = EA Ez ⋆ ∼N (0,In ) wGk ẑ(k) − Gn z ⋆ w 2 w w2 w Gk w Gk 0 ⋆w = EA Ez ⋆ w ẑ(k) − z w 0 w fk 0 G 2 n w w2 X w w = EA Ez ⋆ wGk ẑ(k) − Gk zk⋆ w + σi2 2

i=k+1

n w w2 X † w w = EA Ez ⋆ wGk Ak Gk AGn z ⋆ − Gk zk⋆ w + σi2 2

i=k+1

n w w2 X † w fk G fk ze⋆ − Gk z ⋆ w = EA Ez ⋆ wGk Ak Gk Ak Gk zk⋆ + A + σi2 kw k 2

i=k+1

n w w2 −1 X w w T T T T ⋆ ⋆ ⋆ e f f = EA Ez ⋆ wGk Gk Ak Ak Gk Gk Ak Ak Gk zk + Ak Gk zk − Gk zk w + σi2 2

i=k+1

w w2 −1 −1 w fk G fk ze⋆ − Gk z ⋆ w GTk ATk Ak Gk zk⋆ + Gk GTk ATk Ak Gk = EA Ez ⋆ wGk GTk ATk Ak Gk GTk ATk A kw k 2

n X

σi2

i=k+1 n w2 w X † w fk G fk ze⋆ w + σi2 = EA Ez ⋆ wGk Ak Gk A w k 2

n X i=k+1 n X i=k+1

i=k+1

w2 w † w fk w fk G σi2 + EA wGk Ak Gk A w

w σi2 + EAk wGk

n † w w2 X 2 Ak G k w σi . F

i=k+1

The proof of Lemma 1 relies on the following result of [12]. We use the Frobenius-norm specialization of [12, Theorem 10.5] and include its proof below for the reader’s convenience. The argument follows the proof of [12, Theorem 10.5] and refers to [12, Theorem 9.1 and Propositions 10.1–10.2]. Lemma 11 (Special case of the result in [12]). Let Σ = diag(σ1 , . . . , σn ), σ1 ≥ · · · ≥ σn > 0, and fix 1 ≤ k ≤ m − 2. Partition Σ1 0 Σ= , Σ1 ∈ Rk×k , Σ2 ∈ R(n−k)×(n−k) . 0 Σ2 Let Ω ∈ Rn×m be a standard Gaussian matrix and partition it as Ω1 Ω= , Ω1 ∈ Rk×m , Ω2 ∈ R(n−k)×m . Ω2 Let Y = ΣΩ, and let PY denote the orthogonal projector onto range(Y ). Then k 2 EΩ (I − PY )Σ F ≤ 1 + ∥Σ2 ∥2F . m−k−1 Proof of Lemma 11. We follow the proof of [12, Theorem 10.5], specialized to the present Frobeniusnorm setting and notation. Since m ≥ k + 2, the matrix Ω1 has full row rank almost surely. Applying the deterministic range-finder bound [12, Theorem 9.1] with the Frobenius norm gives 2

(I − PY )Σ F ≤ ∥Σ2 ∥2F + ∥Σ2 Ω2 Ω†1 ∥2F . Conditioning on Ω1 , the matrix Ω2 is an independent standard Gaussian matrix. By the Gaussian Frobenius moment identity [12, Proposition 10.1], EΩ2 ∥Σ2 Ω2 Ω†1 ∥2F = ∥Σ2 ∥2F ∥Ω†1 ∥2F . 21

−1 . Moreover, with It remains to average over Ω1 . Since Ω1 has full row rank, ∥Ω†1 ∥2F = tr (Ω1 Ω⊤ 1) Lemma 18, Ω1 Ω⊤ 1 ∼ Wishartk (Ik , m). Using the mean of inverse-Wishart, 1 Ik , m−k−1

−1 E(Ω1 Ω⊤ = 1)

which is finite because m > k + 1, we obtain EΩ1 ∥Ω†1 ∥2F =

k . m−k−1

Therefore

k ∥Σ2 ∥2F . m−k−1 Taking expectation in the deterministic range-finder bound yields k 2 ∥Σ2 ∥2F . EΩ (I − PY )Σ F ≤ 1 + m−k−1 EΩ ∥Σ2 Ω2 Ω†1 ∥2F =

We now prove Lemma 1. After deriving the exact expression for E(k) in the overdetermined regime, we can verify E(n) ≤ E(k) for 1 ≤ k < m − 1. Proof of Lemma 1. Fix 1 ≤ k ≤ m − 2. By Lemma 10, we have E(k) =

n X

n w † w w w2 X 2 σi2 + EAk wGk Ak Gk w σi . F

i=k+1

Now, by Lemma 12, we get E(k) =

n X

σi2 +

i=k+1

X k σi2 m−k−1

(2.27)

i=k+1

It remains to compare E(k) with the full-model error E(n). By the definition of the full-model estimator, E(n) = EA,x⋆ ∥x̂(n) − x⋆ ∥22 = EA,z ⋆ ∥Gn GTn AT (AGn GTn AT )−1 AGn z ⋆ − Gn z ⋆ ∥22 = EA ∥Gn GTn AT (AGn GTn AT )−1 AGn − Gn ∥2F 2 = EA Gn PGTn AT − In F 2 = EA In − PGTn AT Gn , F

where the last equality follows from the invariance of the Frobenius norm under transposition, together with the symmetry of PG⊤ ⊤ and Gn . Here PG⊤ A⊤ denotes the orthogonal projector onto nA n ⊤ ). Since G = Σ is diagonal, G⊤ A⊤ = ΣA⊤ . Range(G⊤ A n n n Let Ω = A⊤ . Since A has i.i.d. standard Gaussian entries, Ω is a standard Gaussian matrix, so Lemma 11 applies. Thus, PGn A⊤ = PΣΩ . 22

Thus

E(n) = EΩ (In − PΣΩ )Σ F . Applying Lemma 11 with Y = ΣΩ gives E(n) ≤

k 1+ m−k−1

Since

n X

∥Σ2 ∥2F =

∥Σ2 ∥2F .

σi2 ,

i=k+1

we obtain E(n) ≤ 1 +

k m−k−1

X n

σi2 = E(k),

i=k+1

where the last equality is Eq.(2.27) This proves both the closed-form formula for E(k) and the comparison E(n) ≤ E(k). We next record an auxiliary estimate used in the analysis of the overdetermined regime k < m. 2 In this regime, the reconstruction error contains the term T (k) := EAk Gk (Ak Gk )† F , which measures the size of the least-squares reconstruction operator associated with the k-dimensional prior. The following lemma gives an explicit formula for this term. w † w w w2 Lemma 12. Under Lemma 10 assumptions, let T (k) = EAk wGk Ak Gk w . For all k + 1 ≤ m, k , which is monotone increasing in k. T (k) = m−k−1

Proof of Lemma 12. To establish the desired result, recall Ak ∈ Rm×k , Gk ∈ Rk×k . Let Mk = Ak Gk ∈ Rm×k , for k ≤ m, observe that Rank(Mk ) = k, hence Mk has full column rank, and Mk† = (Mk⊤ Mk )−1 Mk⊤ . We have w w w2 † w w w2 w †w wGk Ak Gk w = wGk Mk w F F E D † = Gk Mk , Gk Mk† E D = GTk Gk , Mk† (Mk† )T D E = GTk Gk , (Mk⊤ Mk )−1 Mk⊤ Mk (Mk⊤ Mk )−1 D E = GTk Gk , (Mk⊤ Mk )−1 D E ⊤ −1 = GTk Gk , (G⊤ A A G ) k k k k D E ⊤ −1 −⊤ = GTk Gk , G−1 (A A ) G k k k k D E −1 = I, (A⊤ k Ak ) −1 = Tr (A⊤ k Ak )

Therefore, following the Inverse Wishart Matrix definition, and apply Lemma 19, we know that w † w w w2 Ik k −1 = E EAk wGk Ak Gk w = EAk Tr (A⊤ A ) Ak m−k−1 = m−k−1 , where k < m − 1. It is clear k k F

that T (k) increases monotonically with k. 23

2.6

Boundary divergence at the measurement threshold

In this section, we consider the two critical dimensions k = m − 1 and k = m. We show that E(m − 1) = +∞,

E(m) = +∞.

Proof of Proposition 3. Recall from Section 2.1 that, without loss of generality, we can take Gn = diag(σ1 , . . . , σn ), and let Ak ∈ Rm×k denote the first k columns of A. Fix k ∈ {m−1, m}. Since Ak has full column rank almost surely and Gk is invertible, (Ak Gk )† = † † † G−1 k Ak , and therefore Gk (Ak Gk ) = Ak . The reconstruction-error formula Eq.(2.26) for k ≤ m consequently gives n X † 2 E(k) = 1 + E∥Ak ∥F σi2 . i=k+1

Since k < n and i=k+1 σi2 > 0. It therefore remains to prove that E∥A†k ∥2F = +∞. Let Ak = Qk Rk be the reduced QR decomposition, where Qk ∈ Rm×k has orthonormal columns and Rk ∈ Rk×k is upper triangular with positive diagonal entries. Since A†k = Rk−1 Q⊤ k , we have Pn

−1 2 2 ∥A†k ∥2F = ∥Rk−1 Q⊤ k ∥F = ∥Rk ∥F =

k X

|(Rk−1 )ij |2 ≥ |(Rk−1 )k,k |2 =

i,j=1

1 . (Rk )2k,k

⊤ The second equality follows from Q⊤ k Qk = Ik ; equivalently, right multiplication by Qk preserves the Frobenius norm in this case. The last equality follows from the fact that Rk is invertible and upper triangular, so the diagonal entries of Rk−1 are the reciprocals of those of Rk ; in particular, (Rk−1 )kk = (Rk )−1 kk . By the Bartlett decomposition [15, Theorem 3.2.14] for a standard Gaussian m × k matrix,

(Rk )2j,j ∼ χ2m−j+1 ,

j = 1, . . . , k.

In particular, (Rk )2k,k ∼ χ2m−k+1 . For k ∈ {m − 1, m}, the number of degrees of freedom m − k + 1 is either 2 or 1. Since 1 E 2 = +∞, ν ≤ 2, χν it follows that

" E∥A†k ∥2F ≥ E

1 (Rk )2k,k

# = +∞.

Consequently, E(k) = +∞,

k ∈ {m − 1, m},

which proves the claim.

Acknowledgments The authors thank Sean Gunn for valuable feedback and discussions.

Funding PH acknowledges support from NSF Awards DMS-1848087 and DMS-2022205.

Data Availability No experimental datasets were generated or analyzed in this study. The numerical experiments reported in the paper use synthetically generated data according to the models described in the manuscript.

References [1] Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G. Dimakis. Compressed sensing using generative models. In International Conference on Machine Learning, pages 537–546. PMLR, 2017. [2] Emmanuel Candes and Benjamin Recht. Exact matrix completion via convex optimization. Communications of the ACM, 55(6):111–119, 2012. [3] Emmanuel Candès and Justin Romberg. Sparsity and incoherence in compressive sampling. Inverse Problems, 23(3):969–985, 2007. [4] Emmanuel J. Candes, Justin K. Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics, 59(8):1207–1223, 2006. [5] Emmanuel J. Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52(2):489–509, 2006. [6] Emmanuel J. Candès and Terence Tao. Decoding by linear programming. IEEE Transactions on Information Theory, 51(12):4203–4215, 2005. [7] D.L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289– 1306, 2006. [8] Conor Durkan, Artur Bekasov, Iain Murray, and George Papamakarios. Neural spline flows. In Advances in Neural Information Processing Systems, volume 32, 2019. [9] Maryam Fazel. Matrix rank minimization with applications. PhD thesis, Stanford University, 2002. [10] Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Birkhäuser Basel, 2013. [11] Sean Gunn, Jorio Cocola, Oliver De Candido, Vaggos Chatziafratis, and Paul Hand. Latent Generative Models with Tunable Complexity for Compressed Sensing and other Inverse Problems. arXiv preprint arXiv:2603.07357, 2026. [12] Nathan Halko, Per-Gunnar Martinsson, and Joel A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 53(2):217–288, 2011. 25

[13] Martin Laurenzis. Computational sensing approaches for enhanced active imaging. In ElectroOptical Remote Sensing XII, volume 10796, pages 99–107. SPIE, 2018. [14] Michael Lustig, David L. Donoho, Juan M. Santos, and John M. Pauly. Compressed sensing MRI. IEEE Signal Processing Magazine, 25(2):72–82, 2008. [15] Robb J. Muirhead. Aspects of Multivariate Statistical Theory. John Wiley & Sons, 2009. [16] Irena Orović, Vladan Papić, Cornel Ioana, Xiumei Li, and Srdjan Stanković. Compressive sensing in signal processing: algorithms and transform domain formulations. Mathematical Problems in Engineering, 2016(1):7616393, 2016. [17] Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review, 52(3):471–501, 2010. [18] Dietrich von Rosen. Moments for the inverted wishart distribution. Scandinavian Journal of Statistics, 15(2):97–109, 1988. [19] Yang Song, Liyue Shen, Lei Xing, and Stefano Ermon. Solving inverse problems in medical imaging with score-based generative models. In International Conference on Learning Representations, 2022. [20] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 1996. [21] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010. [22] Carl Wunsch. The ocean circulation inverse problem. Cambridge University Press, 1996. [23] Jong Chul Ye. Compressed sensing mri: a review from signal processing perspective. BMC Biomedical Engineering, 1(1):8, 2019.

MAP interpretation of the reconstruction rule

We briefly explain how the estimator in (1.5) arises from a MAP principle. Let Gk ⊂ Rn denote a k-dimensional generative model. The maximum a posteriori estimator of x⋆ under the prior induced by Gk is 1 ∥y − Ax∥22 + γ 2 log PGk (x) , 2 x∈Range(Gk )

x̂MAP (k) = arg min

where PGk (x) is the density function induced by Gk (x) over Range (Gk ) and evaluated at x, and ∥·∥2 is the ℓ2 norm, and γ denotes the noise level. In the noiseless compressed sensing setting studied here, we consequently analyze the MAP estimator as γ ↓ 0. Suppose A is full rank, the reconstruction rule takes different forms depending on whether the latent dimension is smaller or larger than the number of measurements. Thus, the MAP estimator can be written as:    arg min log PGk (x) s.t. y = Ax, for k ≥ m x∈Range(Gk ) x̂(k) = 2 1  for k < m  arg min 2 ∥y − Ax∥2 , x∈Range(Gk )

It is more convenient to work with the estimator through their latent representation. Thus, in latent coordinates, the MAP estimator can be written as x̂(k) = Gk ẑ(k) where  1 2  arg min 2 ∥zk ∥2 s.t. y = AGk zk , for k ≥ m k zk ∈R ẑ(k) =  for k < m arg min 12 ∥AGk zk − y∥22 ,  zk ∈Rk

This yields the two-regime estimator stated in (1.5).

Proofs of auxiliary results

Lemma 13. Let x ∼ N (0, In ) ∈ Rn then for any matrix M ∈ Rm×n , we have Ex ∥M x∥2 = ∥M ∥2F . Proof of Lemma 13. Ex ∥M x∥2 = Ex ⟨M x, M x⟩ = Ex M T M, xxT = M T M, In = ∥M ∥2F .

Lemma 14. Let x ∼ N (0, Σ) ∈ Rn then for any matrix M ∈ Rm×n , we have Ex ∥M x∥2 = Tr M ΣM T . Proof of Lemma 14. Let Y = M x, then Y ∼ N 0, M ΣM T . Thus, n n X X Ex ∥M x∥2 = EY ∥Y ∥2 = E Y T Y = Yi2 = Var (Yi ) = Tr M ΣM T . i

i=1

Lemma 15. [21] Let X, Y be independent isotropic random vectors in Rn . Then E∥X∥22 = n and E⟨X, Y ⟩2 = n. f ∈ Rm×m ⪰ 0 be positive semidefinite (PSD) matrix, M f is the Lemma 16. Let M ∈ Rm×m ⪰ 0, M perturbation of M , we have f −1 − M −1 + M −1 M fM −1 ≽ 0 M +M Proof of Lemma 16.

i−1 −1 h 1 1 fM − 21 M 12 f = M 2 I + M−2 M M +M −1 1 1 1 fM − 12 = M−2 I + M−2 M M−2

−1 −1 1 1 1 f fM − 12 M − 2 − M −1 M +M − M −1 = M − 2 I + M − 2 M −1 1 − 12 − 12 f − 21 =M I + M MM − I M−2

Thus,

h −1 −1 i 1 fM − 12 f fM −1 = M − 12 I + M − 12 M fM −1 M +M − I M − 2 + M −1 M − M −1 − M −1 M h −1 i 1 1 1 fM − 12 fM − 12 M − 12 = M−2 I + M−2 M − I − M−2 M 1

f is PSD, and M − 2 M fM − 2 hands a basis of eigenvectors, in that basis, everything Since M and M is diagonalible. 1 fM − 21 = U Λ2 U T Let’s M − 2 M 1 fM − 12 )−1 in the basis given by the U Expand (I + M − 2 M 1 fM − 12 )−1 = (I + U Λ2 U T )−1 = U (I + Λ2 )−1 U T (I + M − 2 M 1 fM − 12 in the basis given by U Similarly, expand this linear term I − M − 2 M 1

fM − 2 = I − U Λ2 U T = U (I − Λ2 )−1 U T I − M−2 M

fM − 2 I + M−2 M

−1

−1 1 fM − 12 = U I + Λ2 − I − M−2 M U T − U I − Λ2 U T −1 2 2 =U I +Λ − I −Λ UT

Since we know that x1 is a convex function for x > 0, and 1 − x is the linear approximation around x = 1, so we get: (1 + λ2i )−1 − (1 − λ2i ) ≥ 0 −1 1 1 fM − 12 fM − 12 is PSD. So we know that I + M − 2 M − I − M−2 M 28

h i Claim 1. Let H(k) = EA ^ h(Ak , t) . ∀Ak , h(Ak , t) is monotone. It is sufficient to show that the k−1

monotonicity of H(k) is determined by h(Ak , t). Proof of Claim 1. D = H(k) − H(k − 1) h i h i h(A , t) h(A , t) − E = EA k−1 k ^ ^ A k−1 k−1 h i = EA h(A , t) − h(A , t) k k−1 ^ k−1

Therefore, we know that the sign of D is decided by the sign of h(Ak , t) − h(Ak−1 , t). Theorem 4 (Deterministic error bound [12]). Let A be an m × n matrix with SVD A = U ΣV , and fix k ≥ 0. Choose a test matrix Ω, and construct the sample matrix Y = AΩ. Partition Σ as ∗ Σ1 V1 A=U , Σ1 ∈ Rk×k , Σ2 ∈ R(n−k)×(n−k) . Σ2 V2∗ and define Ω1 and Ω2 via Ω1 = V1⋆ Ω and Ω2 = V2⋆ Ω. Assuming that Ω1 has full row rank, the approximation error satisfies ∥(I − PY ) A∥2F ≤ ∥Σ2 ∥2F + ∥Σ2 Ω2 Ω†1 ∥2F ,

(B.1)

Proof of Theorem 4. Throughout, write Σ = diag(Σ1 , Σ2 ) and recall " # " # ⋆ Σ V Σ Ω 1 1 1 1 Ã := U ⋆ A = ΣV ⋆ = , Ỹ := ÃΩ = , Σ2 V2⋆ Σ2 Ω2 where the block sizes are k and n − k. We note that the left factor U is irrelevant. Because Ỹ = U ⋆ Y and orthogonal projectors transform by conjugation, PỸ = U ⋆ PY U . Hence (I − PỸ )Ã = U ⋆ (I − PY )A, and since the Frobenius norm is unitarily invariant, (I − PY )A F = (I − PỸ )Ã F . It therefore suffices to bound ∥(I − PỸ )Ã∥2F . We assume k is chosen so that every diagonal entry of Σ1 is strictly positive. If not, then Σ2 = 0 by the ordering of the singular values, and both blocks of Ã lie in the row space of Ω1 (which has full row rank), so Σ1 V1⋆ Σ1 Ω1 range(Ã) = range = range = range(Ỹ ). 0 0 In that case (I − PỸ )Ã = 0 and the bound holds trivially (both sides vanish). So assume Σ1 is invertible. The idea is to replace Ỹ by a matrix whose top block is the identity, obtained by “flattening” the top spectrum. Since Ω1 has full row rank we have Ω1 Ω†1 = I, so define " # I † −1 Z := Ỹ Ω1 Σ1 = , F := Σ2 Ω2 Ω†1 Σ−1 1 . F 29

(The top block is Σ1 Ω1 Ω†1 Σ−1 1 = I; the bottom block is F .) Because Z is Ỹ times a matrix on the right, range(Z) ⊆ range(Ỹ ). Enlarging the range can only decrease the residual of the associated projector, so (B.2) (I − PỸ )Ã F ≤ (I − PZ )Ã F . The next step is to find the explicit form of the complementary projector I − PZ . The matrix Z has full column rank, so PZ = Z(Z ⋆ Z)−1 Z ⋆ with Z ⋆ Z = I + F ⋆ F . A direct block computation gives " # I − (I + F ⋆ F )−1 −(I + F ⋆ F )−1 F ⋆ , I − PZ = −F (I + F ⋆ F )−1 I − F (I + F ⋆ F )−1 F ⋆ whose block structure conforms with the partition of Σ. Write B := −(I + F ⋆ F )−1 F ⋆ for the off-diagonal block. Now, we can find the semidefinite bound on the projector. Set M := F ⋆ F ⪰ 0. For the diagonal blocks: • Top-left: for any psd M one has I − (I + M )−1 ≼ M (equivalently (I + M )−1 ⪰ I − M , which µ2 1 follows entrywise on eigenvalues from 1+µ − (1 − µ) = 1+µ ≥ 0). Thus the top-left block is ≼ F ⋆F . • Bottom-right: F (I + F ⋆ F )−1 F ⋆ ⪰ 0, so this block is ≼ I. Since replacing the two diagonal blocks by these upper bounds leaves the off-diagonal blocks unchanged, the difference is block-diagonal with psd diagonal blocks, hence psd. Therefore " # F ⋆F B I − PZ ≼ . B⋆ I Congruence preserves the semidefinite order, so conjugating by Σ = diag(Σ1 , Σ2 ) gives " # ⋆F ⋆F Σ ⋆ BΣ Σ Σ 1 2 1 1 Σ⋆ (I − PZ )Σ ≼ . Σ⋆2 B ⋆ Σ1 Σ⋆2 Σ2 Now use Ã = ΣV ⋆ together with unitary invariance of the trace: 2 (I − PZ )Ã F = Tr Ã⋆ (I − PZ )Ã = Tr Σ⋆ (I − PZ )Σ . The trace is monotone with respect to ≼ and picks out only the diagonal blocks, so 2 2 Tr Σ⋆ (I − PZ )Σ ≤ Tr Σ⋆1 F ⋆ F Σ1 + Tr Σ⋆2 Σ2 = F Σ1 F + Σ2 F . Finally, by definition of F , † F Σ1 = Σ2 Ω2 Ω†1 Σ−1 1 Σ1 = Σ2 Ω2 Ω1 ,

so ∥F Σ1 ∥2F = ∥Σ2 Ω2 Ω†1 ∥2F . Combining all together, 2

(I − PY )A F = (I − PỸ )Ã F ≤ (I − PZ )Ã F ≤ Σ2 F + Σ2 Ω2 Ω†1 F , which is the asserted bound. 30

Wishart and Inverse Wishart Distributions

In this appendix we collect the basic definitions and facts on the Wishart and Inverse Wishart distributions that are used in the main text. Proofs of these results can be found in standard references on multivariate statistics (e.g., Muirhead, 1982).

C.1

Wishart distribution

Definition 1 (Wishart distribution). Let X ∈ Rn×p have i.i.d. rows xi ∼ N (0, Σ), where Σ ∈ Rp×p is positive definite. The random matrix n X W = X ⊤X = xi x⊤ i i=1

is said to follow a Wishart distribution with n degrees of freedom and scale matrix Σ, written W ∼ Wp (Σ, n). Lemma 17 (Basic Properties of Wishart Matrices). If W ∼ Wp (Σ, n), then: 1. W is almost surely symmetric positive semidefinite. 2. E[W ] = nΣ. 3. If n ≥ p, then W is almost surely invertible. Remark 1. When Σ = Ip , W is the sample covariance matrix (up to a factor of n) for standard Gaussian data.

C.2

Inverse Wishart distribution

Definition 2 (Inverse Wishart distribution). A random matrix S ∈ Rp×p is said to follow an Inverse Wishart distribution with scale matrix Ψ and n degrees of freedom, written S ∼ Wp−1 (Ψ, n), if S = W −1 where W ∼ Wp (Ψ−1 , n). Lemma 18 (Moments of the inverse Wishart). If S ∼ Wp−1 (Ψ, n) and n > p + 1, then Ψ . n−p−1 Remark 2. The Inverse Wishart distribution is commonly used as a conjugate prior for covariance matrices in Bayesian statistics. E[S] =

C.3

Identities used in the paper

The following identities are used repeatedly in Sections 3.4. Lemma 19 (Useful expectations). If W ∼ Wp (Σ, n) with n > p + 1, then p 1 Σ−1 , E Tr(W −1 ) = Tr(Σ−1 ). E[W −1 ] = n−p−1 n−p−1 Lemma 20 (Concentration). As n → ∞, 1 a.s. W −−−→ Σ, n that is, the Wishart law concentrates around nΣ. 31

Supplementary experiment result from Section 1.2

Figure 2: Relative reconstruction error in compressed sensing with diagonal generator matrix. It shows reconstruction error versus model dimension k in compressed sensing with n = 150, m = 30. The generator matrix Gn has diagonal structure with exponentially decaying singular values. The error exhibits three regimes predicted by our theory: a U-shaped behavior for k < m, a sharp peak at the interpolation threshold k = m, and monotone decay for k > m . Alt text: Alt text: A line plot of relative reconstruction error versus latent dimension. The horizontal axis shows the latent dimension, and the vertical axis shows the relative reconstruction error. The plot contains data points connected by lines across the full range of latent dimensions.

Full-Model Optimality for Tunable Linear Generative Priors in Compressed Sensing

Analyze & explore related research in Conceptio

Related documents