CS Paper Radar

Large-System Analysis of Sparse Bayesian Learning

Fangqing Xiao, Dirk T. M. Slock

eess.SP cs.IT ·submitted 2026-09-06 12:11 UTC · v1

Abstract

Sparse Bayesian learning is widely used for sparse linear inverse problems, yet its large-system stationary behavior remains poorly understood because all variance hyperparameters are estimated from the same data. We study classical sparse Bayesian learning, formulated as evidence maximization (type-II maximum likelihood), for underdetermined linear models with sensing matrices having independent and identically distributed Gaussian entries, Gaussian measurement noise, and an unknown deterministic signal sequence. Hyperparameter reoptimization induces a nonvanishing feedback term: a typical coordinate obeys a reoptimization-corrected scalar Gaussian law whose signal coefficient is governed by the normalized adaptive response rather than the frozen resolvent trace. A one-coordinate leave-one-out construction gives an exact conditional Gaussian law, which is transferred to a selected full stationary branch without assuming asymptotic closeness of the reduced and full stationary vectors. Combining this law with the Karush--Kuhn--Tucker conditions of the evidence objective yields a generally set-valued scalar relation and three branchwise large-system consistency relations. If the model noise variance is jointly estimated by evidence maximization, interior joint stationarity yields an exact finite-dimensional equality between the normalized residual energy and normalized resolvent trace. When the limiting signal law has nonzero mass at zero, this identity further yields a parameter-free asymptotic chi-square null law. Under an additional differentiability condition on the selected scalar branch, the large-system characterization also gives a closed relation for the reconstruction error of the posterior mean. The analysis is stationary-point based and permits multiple stationary branches.

Closest papers

Nearest neighbours by meaning across the whole index.

Efficient SCA Algorithms for Sparse Bayesian Learning

eess.SP ·2026-10-26 ·Esa Ollila, Majdoddin Esfandiari, Daniel P. Palomar, Xinjue Wang
theory similarity 0.69
Abstract

Type-II sparse Bayesian learning (SBL) for the multiple measurement vector model recovers a sparse signal power vector by minimizing the marginal negative log-likelihood via the expectation-maximization (EM) algorithm, referred to as M-SBL. We revisit the covariance learning (CL) problem and develop three parallel first-order algorithms within the successive convex approximation (SCA) framework. CL-SCA minimizes per-coordinate surrogates formed by partially linearizing the log-determinant term, while CL-FP uses a damped projected fixed-point iteration derived from stationarity conditions. Both methods have closed-form updates. We prove that the fixed points of both update maps are exactly the KKT points of the CL problem, that each update direction satisfies a quantitative descent inequality, that the damped iterates achieve sufficient decrease with an $\mathcal{O}(T^{-1/2})$ best-iterate stationarity rate, and we derive a backtracking rule that retains this rate without step-size tuning. If damping factors are bounded away from zero, the residual vanishes along the whole sequence and every limit point is a KKT point. Local analysis motivates CL-Hyb, which combines CL-SCA and CL-FP. Experiments on device activity detection in massive random access show that CL-Hyb-bt matches the best CL solvers' accuracy at a fraction of the runtime and is over an order of magnitude faster than EM.

0.44

Adaptive multi-resolution Gaussian processes: Scalable exact inference with naturally data-sparse covariance matrices

cs.AI stat.MLcs.LG ·2026-09-24 ·Yanchuang Cao, Jun Liu, Tengchao Yu, Heng Yong
similarity 0.65
Abstract

Gaussian processes constitute a cornerstone of probabilistic machine learning, yet scaling them to large datasets typically forces a trade-off between computational efficiency and model fidelity. This work bridges this gap by presenting an adaptive multi-resolution Gaussian process framework that is both scalable and exact. Our key innovation is constructing a naturally data-sparse covariance matrix with adaptive multi-resolution basis functions. These basis functions are directly anchored to samples, eliminating the need for auxiliary points. By shrinking the support domains of multi-resolution basis, the matrix block sizes are limited, guaranteeing sparsity. The inverse of the data-sparse covariance matrix is computed exactly and efficiently via the sparse Cholesky inverse algorithm. To further improve predictive uncertainties, we construct an augmented basis function. Theoretical analysis and numerical experiments demonstrate that our model achieves exact inference with $\mathcal{O}(n \log^2 n)$ training cost and $\mathcal{O}(\log^d n)$ prediction cost, establishing a principled framework for scalable and high-fidelity Gaussian process regression.

0.17

Sparsity by Default: The Theory and Practice of ARD in Gaussian Process Regression for Variable Selection

cs.LG stat.ML ·2026-09-27 ·Jia Cai
surveyposition similarity 0.60
Abstract

Automatic relevance determination (ARD) is the standard device for input selection in Gaussian process (GP) regression. By giving the covariance kernel a separate lengthscale for every input and learning those lengthscales by maximizing the marginal likelihood, ARD lets the data decide which coordinates matter: irrelevant inputs receive very large lengthscales and are effectively switched off. We trace this mechanism to the Bayesian Occam's razor embodied in the marginal likelihood, derive the gradient through which it prunes inputs, and emphasize that ARD delivers effective rather than exact sparsity. We review the algorithms used in practice and the rules that turn lengthscales into selections, and we survey the asymptotic theory, distinguishing the fixed-domain identifiability obstruction on the lengthscales from the high-dimensional selection-consistency guarantees recently established for hierarchical GP priors, and noting what remains open for plain ARD. We compare ARD with spike-and-slab priors, sparse axis-aligned and global-local shrinkage priors including the Bayesian lasso and horseshoe, penalized likelihood kriging, sensitivity and projection criteria, and additive kernels. We argue that ARD endures because of its seamless integration with kernel learning, universal software support, and low cost, and we close with its limitations and remedies.

0.30

Quantitative Universality of Approximate Message Passing for Rank-One Quadratic Sensing

cs.IT stat.ML ·2026-10-04 ·Duy Thuc Nguyen, Yue M. Lu, Subhabrata Sen
similarity 0.60
Abstract

Approximate Message Passing (AMP) algorithms are attractive as they are computationally efficient and simultaneously admit a precise characterization in terms of the low-dimensional "state-evolution" recursion. In this work, we establish quantitative universality for AMP with centered rank-one sensing matrices $Z_i=(x_ix_i^\top-I_d)/\sqrt d$, where $x_i$ are independent standard Gaussian vectors. These matrices arise in quadratic regression and learning quadratic neural networks. Their normalized vectorizations have isotropic covariance in dimension $p=d(d+1)/2$, but strongly dependent coordinates. For linear observations with Gaussian noise and prescribed smooth, bounded spectral denoisers, we compare rank-one sensing with a covariance-matched isotropic Gaussian ensemble. At a fixed iteration horizon, with $n\leq Cp$ and uniform bounds on the normalized signal energy, initialization, coefficients, and first four denoiser derivatives, normalized signal overlaps, cross-time overlaps, and smooth linear spectral statistics differ by $O(d^{-1/2})$ in every fixed $L^m$. This yields universality of the normalized mean-squared error, fixed spectral moments, and empirical spectral distributions. Whenever the Gaussian observables admit a joint state-evolution limit, the same predictions hold under rank-one sensing. The proof uses columnwise Lindeberg replacement, leave-one-out analysis, smooth spectral expansions, and high-moment concentration. For prescribed smooth spectral denoisers, the result establishes the AMP universality conjectured by Maillard et al. (arXiv:2408.03733).

0.19

Diffusion Models are Provably Efficient Priors for Sparse Recovery

cs.IT stat.MLcs.LGmath.OC ·2026-11-18 ·Ivan Lee, Xingyu Xu, Yuejie Chi
similarity 0.60
Abstract

Diffusion models have transformed generative modeling through their ability to capture and generate samples from complex data distributions. This success has spurred substantial interest in using pretrained diffusion models as expressive priors for highly ill-posed inverse problems in imaging and sensing. Despite strong empirical performance, theoretical understanding of this approach remains limited: existing guarantees are often asymptotic or entail prohibitive computational costs in the worst case. In this paper, we address this gap by studying sparse recovery from a small number of linear measurements, a classical problem in compressed sensing. We show that, given an accurate diffusion model capturing a sparsity-promoting Bernoulli-Gaussian prior, a likelihood-guided annealed Langevin sampler provably recovers the sparse signal in polynomial time with near-optimal sample complexity for a broad family of random and deterministic sensing matrices. When the signal is indeed drawn from the postulated prior, we further establish total variation guarantees for posterior sampling after a final denoising step. These results lay a theoretical foundation for statistically and computationally efficient inverse solvers with diffusion priors.

0.23

Information-Theoretic Limits for Rectangular Spiked Matrix Models with Rotationally Invariant Noise

cs.IT cond-mat.dis-nnmath.ST ·2026-10-12 ·Qun Chen, Rudy Skerk, Jean Barbier, Francesco Camilli, Junjie Ma +1 more
similarity 0.60
Abstract

We study the information-theoretic limits of inference in rectangular rank-one spiked matrix models with additive rotationally invariant noise, thereby going beyond the standard assumption of independent noise entries. Using the replica method from statistical physics, we derive a variational formula for the mutual information between the signal and the data, together with a system of saddle point equations predicting the minimum mean squared error in estimating the rank-one spike. We further show that, in the Bayes-optimal setting, these saddle point equations coincide with the fixed point equations of the state evolution of a recently proposed orthogonal approximate message passing algorithm with Bayes-optimal denoisers. This equivalence provides an algorithmic interpretation of the replica prediction and supports the Bayes-optimality of orthogonal approximate message passing whenever the relevant fixed point is unique. Numerical evaluations of the saddle point equations for several rotationally invariant noise ensembles and signal priors, together with finite-size simulations of the algorithm, confirm the asymptotic predictions. They illustrate both regimes with a unique informative fixed point, where orthogonal approximate message passing is predicted to attain the minimum mean squared error, and regimes with multiple fixed points, where a statistical-to-computational gap exists.

0.39

Nuclear Norm-Regularized Bayesian Matrix Completion

cs.LG stat.ML ·2026-09-24 ·Calvin Tolbert
similarity 0.59
Abstract · 40 pages, 7 figures

Nuclear-norm-regularized least squares is a standard approach to matrix completion, but it yields only a point estimate. Its Bayesian counterpart, a prior combining the nuclear norm with a Frobenius-norm term, gives a strongly log-concave though nonsmooth posterior when the noise precision is known. In practice the precision is unknown, and placing a truncated Jeffreys prior on it makes the joint posterior neither log-concave nor smooth. To our knowledge, we give the first sampler for this model with an explicit non-asymptotic guarantee: its output is within a prescribed total-variation or Wasserstein distance of the posterior on the matrix after a number of steps polynomial in the matrix dimensions and the reciprocal of the target accuracy. The sampler never targets a continuous distribution that is not strongly log-concave. It discretizes the precision onto a grid, estimates its posterior by thermodynamic integration along the tilted conditional posteriors of the matrix, and bounds the error this propagates to the posterior on the matrix. The approach applies whenever non-log-concavity is confined to a bounded scalar hyperparameter and the conditional distributions are strongly log-concave with smooth-plus-Lipschitz potentials. Our result establishes feasibility; the polynomial complexity is not intended as a practical algorithm at current problem scales.

0.26

Sparse Bayesian Sensing for Antenna Arrays with Per-Element Gain, Phase, and Position Errors

eess.SP ·2026-11-05 ·Patrick Hödl, Erik Leitinger, Klaus Witrisal
benchmarktheory similarity 0.59
Abstract

The sensing capabilities of 6G wireless communication systems rely on accurate models of phased-array antennas. However, hardware imperfections can introduce a mismatch between the assumed and the actual array response, leading to performance degradations. To prevent these, we propose a parametric, model-based sparse Bayesian learning (SBL) channel estimation algorithm with integrated self-calibration, which accounts for antenna-position deviations as well as gain and phase offsets. The algorithm learns channel parameters such as delay and direction-of-arrival (DoA), together with per-antenna complex weights and position deviations based on fast variational SBL with dictionary refinement. We derive a marginal-likelihood-based cost function for the antenna position update. The sensing performance is evaluated in terms of the optimal subpattern-assignment (OSPA) metric of the delay and DoA. The proposed method approaches a benchmark based on the derived hybrid Cramér--Rao lower bound (HCRLB) in the considered single-snapshot sensing scenarios. Finally, we investigate the influence of the detection threshold using synthetic and measurement data. On single-snapshot measurements, our algorithm reduces the position OSPA from about 6 m to 0.2 m for an appropriately chosen threshold.

0.31