Despite a large and significant body of recent work focusing on the hyperparameter tuning of regularized models in the high dimensional regime, a theoretical understanding of this problem for non-differentiable penalties such as generalized LASSO and nuclear norm is missing. In this paper we resolve this challenge. We study the hyperparameter tuning problem in the proportional high dimensional regime where both the sample size $n$ and number of features $p$ are large, and $n/p$ and the signal-to-noise ratio (per observation) remain finite. To achieve this goal, we first provide finite-sample upper bounds on the expected squared error of leave-one-out cross-validation (LO) in estimating the out-of-sample risk. Building on this result, we establish the consistency of the hyperparameter tuning method that is based on minimizing LO’s estimate. Our simulation results confirm the accuracy and sharpness of our theoretical results.

The goal of phase-only compressed sensing is to recover a structured signal$\mathbf{x}$from the phases$\mathbf{z}=\text{sign}(\boldsymbol{\Phi} \mathbf{x})$, where$\boldsymbol{\Phi}$is a complex-valued sensing matrix. As demonstrated in prior studies, exact reconstruction of the signal's direction is possible by reformulating the problem as a linear compressed sensing problem and applying basis pursuit (i.e., constrained norm minimization). For$\Phi$with i.i.d. complex-valued Gaussian entries, this paper demonstrates that the phase transition is approximately determined by the statistical dimension of the descent cone associated with a signal-dependent norm. Leveraging this insight, we derive asymptotically precise formulas for the phase transition locations in phase-only sensing of both sparse signals and lowrank matrices. Our results prove that the minimum number of measurements required for exact recovery is smaller for phaseonly measurements than for traditional linear compressed sensing. For instance, in recovering a 1 -sparse signal with sufficiently large dimension, phase-only compressed sensing requires approximately 68 % of the measurements needed for linear compressed sensing. This result disproves earlier conjectures suggesting that the two phase transitions coincide. Our proof hinges on the Gaussian min-max theorem and the key observation that, up to a signaldependent orthogonal transformation, the sensing matrix in the reformulated problem behaves as a nearly Gaussian matrix.

Machine unlearning focuses on the computationally efficient removal of specific training data from trained models, ensuring that the influence of forgotten data is effectively eliminated without the need for full retraining. Despite advances in low-dimensional settings, where the number of parameters \( p \) is much smaller than the sample size \( n \), extending similar theoretical guarantees to high-dimensional regimes remains challenging. We study an unlearning algorithm that starts from the original model parameters and performs a theory-guided sequence of Newton steps. After this update, carefully scaled isotropic Laplacian noise is added to the estimate to ensure that any (potential) residual influence of the deletion set is completely removed. We show that when both \( n, p \to \infty \) with a fixed ratio \( n/p \), significant theoretical and computational obstacles arise due to the interplay between the complexity of the model and the finite signal-to-noise ratio. Finally, we show that, unlike in low-dimensional settings where one Newton step suffices, in high-dimensional problems at least two Newton steps are required to effectively unlearn a fixed number of data points, and even more steps are required when the deletion set scales with $n$. We provide numerical experiments to support the theoretical claims of the paper.

We study the problem of estimating a function in the presence of both speckle and additive noises, commonly referred to as the de-speckling problem. Although additive noise has been thoroughly explored in nonparametric estimation, speckle noise, prevalent in applications such as synthetic aperture radar, ultrasound imaging, and digital holography, has not received as much attention. Consequently, there is a lack of theoretical investigations into the fundamental limits of mitigating the speckle noise. This paper is the first step in filling this gap. Our focus is on investigating the minimax estimation error for estimating a β-H¨older continuous function and determining the rate of the minimax risk. Specifically, ifnrepresents the number of data points,fdenotes the underlying function to be estimated, νnis an estimate off, and σnis the standard deviation of the additive Gaussian noise, then inf νnsupfEf∥νn−f∥22decays at the rate (max(1, σ4n)/n)2β/2β+1. Comparing this rate with the rate achieved under purely additive noise, namely (σ2n/n) 2β/2β+1, leads to the following insights: (i) When σn= ω(1), the additive noise appears to be the dominant component in the de-speckling problem. However, the presence of speckle noise significantly complicates the task of mitigating its effects. As a result, the risk increases from the rate (σ2n/n) 2β/2β+1 , which characterizes the problem with only additive noise, to (σ4n/n) 2β/2β+1 in the presence of both speckle and additive noise. (ii) When σn=o(1), the variance of the additive noise does not contribute to the risk in the de-speckling problem. This suggests that, in this regime, speckle noise is the primary bottleneck. Interestingly, the resulting risk rate matches the rate for mitigating purely additive noise with σn= Θ(1). (iii) When σn= Θ(1), the two rates coincide, suggesting that both the speckle noise and additive noise are contributing to the overall error.

We investigate both the theoretical and algorithmic aspects of likelihood-based methods for recovering a complex-valued signal from multiple sets of measurements, referred to as looks, affected by speckle (multiplicative) noise. Our theoretical contributions include establishing the first existing theoretical upper bound on the Mean Squared Error (MSE) of the maximum likelihood estimator under the deep image prior hypothesis. Our theoretical results capture the dependence of MSE upon the number of parameters in the deep image prior, the number of looks, the signal dimension, and the number of measurements per look. On the algorithmic side, we introduce the concept of bagged Deep Image Priors (Bagged-DIP) and integrate them with projected gradient descent. Furthermore, we show how employing Newton-Schulz algorithm for calculating matrix inverses within the iterations of PGD reduces the computational complexity of the algorithm. We will show that this method achieves the state-of-the-art performance.

The out-of-sample error (OO) is the main quantity of interest in risk estimation and model selection. Leave-one-out cross validation (LO) offers a (nearly) distribution-free yet computationally demanding approach to estimate OO. Recent theoretical work showed that approximate leave-one-out cross validation (ALO) is a computationally efficient and statistically reliable estimate of LO (and OO) for generalized linear models with differentiable regularizers. For problems involving non-differentiable regularizers, despite significant empirical evidence, the theoretical understanding of ALO’s error remains unknown. In this paper, we present a novel theory for a wide class of problems in the generalized linear model family with non-differentiable regularizers. We bound the error$|{\mathrm { ALO}}-{\mathrm { LO}}|$in terms of intuitive metrics such as the size of leave-i-out perturbations in active sets, sample size n, number of features p and regularization parameters. As a consequence, for the$\ell _{1}$-regularized problems, we show that$|{\mathrm { ALO}}-{\mathrm { LO}}| \xrightarrow {p\rightarrow \infty } 0$while$n/p$and signal-to-noise ratio (SNR) are bounded.

Since its development, the minimax framework has been one of the corner stones of theoretical statistics, and has contributed to the popularity of many well-known estimators, such as the regularized M-estimators for high-dimensional problems. In this paper, we will first show through the example of sparse Gaussian sequence model, that the theoretical results under the classical minimax framework are insufficient for explaining empirical observations. In particular, both hard and soft thresholding estimators are (asymptotically) minimax, however, in practice they often exhibit sub-optimal performances at various signal-to-noise ratio (SNR) levels. The first contribution of this paper is to demonstrate that this issue can be resolved if the signal-to-noise ratio is taken into account in the construction of the parameter space. We call the resulting minimax framework the signal-to-noise ratio aware minimaxity. The second contribution of this paper is to showcase how one can use higher-order asymptotics to obtain accurate approximations of the SNR-aware minimax risk and discover minimax estimators. The theoretical findings obtained from this refined minimax framework provide new insights and practical guidance for the estimation of sparse signals.

We consider an inverse problem$\boldsymbol {y}= f(\boldsymbol {Ax})$, where$\boldsymbol {x}\in \mathbb {R}^{n}$is the signal of interest,$\boldsymbol {A}$is the sensing matrix,$f$is a nonlinear function and$\boldsymbol {y} \in \mathbb {R}^{m}$is the measurement vector. In many applications, we have some level of freedom to design the sensing matrix$\boldsymbol {A}$, and in such circumstances we could optimize$\boldsymbol {A}$to achieve better reconstruction performance. As a first step towards optimal design, it is important to understand the impact of the sensing matrix on the difficulty of recovering$\boldsymbol {x}$from$\boldsymbol {y}$. In this paper, we study the performance of one of the most successful recovery methods, i.e., the expectation propagation (EP) algorithm. We define a notion of spikiness for the spectrum of$\boldsymbol {A}$and show the importance of this measure for the performance of EP. We show that whether a spikier spectrum can hurt or help the recovery performance depends on$f$. Based on our framework, we are able to show that, in phase-retrieval problems, matrices with spikier spectrums are better for EP, while in 1-bit compressed sensing problems, less spiky spectrums lead to better performance. Our results unify and substantially generalize existing results that compare Gaussian and orthogonal matrices, and provide a platform towards designing optimal sensing systems.

This paper presents a correction to Theorem 2 in[1]which follows from fixing an error inLemma 5 and aminor correction in the constant ofLemma 3. Despite modifications to upper bounds and constants, the core conclusions of the original paper remain unaffected. The revised proofs now feature precise constants for clarity, maintaining the original findings’ integrity.

Speckle or multiplicative noise is a critical issue in coherence-based imaging systems, such as synthetic aperture radar and optical coherence tomography. Existence of speckle noise considerably limits the applicability of such systems by degrading their performance. On the other hand, the sophistications that arise in the study of multiplicative noise have so far impeded theoretical analysis of such imaging systems. As a result, the current acquisition technology relies on heuristic solutions, such as oversampling the signal and converting the problem into a denoising problem with multiplicative noise. This paper attempts to bridge the gap between theory and practice by providing the first theoretical analysis of such systems. To achieve this goal the log-likelihood function corresponding to measurement systems with speckle noise is characterized. Then employing compression codes to model the source structure, for the case of under-sampled measurements, a compression-based maximum likelihood recovery method is proposed. The mean squared error (MSE) performance of the proposed method is characterized and is shown to scale as$O\left({\sqrt {\frac{k \log n }{ m}}}\right)$, where$k$,$m$and$n$denote the intrinsic dimension of the signal class according to the compression code, the number of observations, and the ambient dimension of the signal, respectively. This result, while in contrast to imaging systems with additive noise in which MSE scales as$O\left({{\frac{k \log n }{ m}}}\right)$, suggests that if the signal class is structured (i.e.,$k \ll n$), accurate recovery of a signal from under-determined measurements is still feasible, even in the presence of speckle noise. Simulation results are presented that suggest image recovery under multiplicative noise is inherently more challenging than additive noise, and that the derived theoretical results are sharp.

We consider a nonlinear inverse problem $\mathbf{y}= f(\mathbf{Ax})$, where observations $\mathbf{y} \in \mathbb{R}^m$ are the componentwise nonlinear transformation of $\mathbf{Ax} \in \mathbb{R}^m$, $\mathbf{x} \in \mathbb{R}^n$ is the signal of interest and $\mathbf{A}$ is a known linear mapping. By properly specifying the nonlinear processing function, this model can be particularized to many signal processing problems, including compressed sensing and phase retrieval. Our main goal in this paper is to understand the impact of sensing matrices, or more specifically the spectrum of sensing matrices, on the difficulty of recovering $\mathbf{x}$ from $\mathbf{y}$. Towards this goal, we study the performance of one of the most successful recovery methods, i.e. the expectation propagation algorithm (EP). We define a notion for the spikiness of the spectrum of $\mathbf{A}$ and show the importance of this measure in the performance of the EP. Whether the spikiness of the spectrum can hurt or help the recovery performance of EP depends on $f$. We define certain quantities based on the function $f$ that enables us to describe the impact of the spikiness of the spectrum on EP recovery. Based on our framework, we are able to show that for instance, in phase-retrieval problems, matrices with spikier spectrums are better for EP, while in 1-bit compressed sensing problems, less spiky (flatter) spectrums offer better recoveries. Our results unify and substantially generalize the existing results that compare sub-Gaussian and orthogonal matrices, and provide a platform toward designing optimal sensing systems.

Phase retrieval refers to the problem of recovering a signal$ {x}_{\star }\in \mathbb {C}^{n}$from its phaseless measurements$\text {y}_{\text {i}}=| {a}_{i}^{ \mathsf {H}} {x}_{\star }|$, where$\{ {a}_{\text {i}}\}_{\text {i}=1}^{ {m}}$are the measurement vectors. Spectral method is widely used for initialization in many phase retrieval algorithms. The quality of spectral initialization can have a major impact on the overall algorithm. In this paper, we focus on the model where$ {A}=[ {a}_{1},\ldots, {a}_{ {m}}]^{ \mathsf {H}}$has orthonormal columns, and study the spectral initialization under the asymptotic setting$ {m}, {n}\to \infty $with$ {m}/ {n}\to \delta \in (1,\infty)$. We use the expectation propagation framework to characterize the performance of spectral initialization for Haar distributed matrices. Our numerical results confirm that the predictions of the EP method are accurate for not-only Haar distributed matrices, but also for realistic Fourier based models (e.g. the coded diffraction model). The main findings of this paper are the following: 1) There exists a threshold on$\delta $(denoted as$\delta _{ \mathrm {weak}}$) below which the spectral method cannot produce a meaningful estimate. We show that$\delta _{ \mathrm {weak}}=2$for the column-orthonormal model. In contrast, previous results by Mondelli and Montanari show that$\delta _{ \mathrm {weak}}=1$for the i.i.d. Gaussian model. 2) The optimal design for the spectral method coincides with that for the i.i.d. Gaussian model, where the latter was recently introduced by Luo, Alghamdi and Lu.

Risk estimation is at the core of many learning systems. The importance of this problem has motivated researchers to propose different schemes, such as cross validation, generalized cross validation, and Bootstrap. The theoretical properties of such estimators have been extensively studied in the low-dimensional settings, where the number of predictors p is much smaller than the number of observations n. However, a unifying methodology accompanied with a rigorous theory is lacking in high-dimensional settings. This paper studies the problem of risk estimation under the moderately high-dimensional asymptotic setting n,p → ∞ and n/p → δ > 1 ( δ is a fixed number), and proves the consistency of three risk estimators that have been successful in numerical studies, i.e., leave-one-out cross validation (LOOCV), approximate leave-one-out (ALO), and approximate message passing (AMP)-based techniques. A corner stone of our analysis is a bound that we obtain on the discrepancy of the `residuals' obtained from AMP and LOOCV. This connection not only enables us to obtain a more refined information on the estimates of AMP, ALO, and LOOCV, but also offers an upper bound on the convergence rate of each estimator.

We study the problem of out-of-sample risk estimation in the high dimensional regime where both the sample size $n$ and number of features $p$ are large, and $n/p$ can be less than one. Extensive empirical evidence confirms the accuracy of leave-one-out cross validation (LO) for out-of-sample risk estimation. Yet, a unifying theoretical evaluation of the accuracy of LO in high-dimensional problems has remained an open problem. This paper aims to fill this gap for penalized regression in the generalized linear family. With minor assumptions about the data generating process, and without any sparsity assumptions on the regression coefficients, our theoretical analysis obtains finite sample upper bounds on the expected squared error of LO in estimating the out-of-sample error. Our bounds show that the error goes to zero as $n,p \rightarrow \infty$, even when the dimension $p$ of the feature vectors is comparable with or greater than the sample size $n$. One technical advantage of the theory is that it can be used to clarify and connect some results from the recent literature on scalable approximate LO.

It has been proved that for all stationary and ergodic processes the average Kolmogorov complexity of the first n observations converges almost surely to its Shannon's conditional entropy. This paper studies the convergence rate of this asymptotic result. In particular, we show that if the process satisfies certain mixing conditions, then a central limit theorem will be respected. Furthermore, we show that under slightly stronger mixing conditions one may obtain non-asymptotic concentration bounds for the Kolmogorov complexity.

Compressive phase retrieval refers to the problem of recovering a structured n-dimensional complex-valued vector from its phase-less under-determined linear measurements. The non-linearity of the measurement process makes designing theoretically-analyzable efficient phase retrieval algorithms challenging. As a result, to a great extent, existing recovery algorithms only take advantage of simple structures such as sparsity and its convex generalizations. The goal of this article is to move beyond simple models through employing compression codes. Such codes are typically developed to take advantage of complex signal models to represent the signals as efficiently as possible. In this work, it is shown how an existing compression code can be treated as a black box and integrated into an efficient solution for phase retrieval. First, COmpressive PhasE Retrieval (COPER) optimization, a computationally-intensive compression-based phase retrieval method, is proposed. COPER provides a theoretical framework for studying compression-based phase retrieval. The number of measurements required by COPER is connected to κ, the α-dimension (closely related to the ratedistortion dimension) of a given family of compression codes. To finds the solution of COPER, an efficient iterative algorithm called gradient descent for COPER (GD-COPER) is proposed. It is proven that under some mild conditions on the initialization and the compression code, if the number of measurements is larger than Cκ2log2n, where C is a constant, GD-COPER obtains an accurate estimate of the input vector in polynomial time. In the simulation results, JPEG2000 is integrated in GD-COPER to confirm the state-of-the-art performance of the resulting algorithm on real-world images.

Phase retrieval refers to algorithmic methods for recovering a signal from its phaseless measurements. There has been recent interest in understanding the performance of local search algorithms that work directly on the non-convex formulation of the problem. Due to the non-convexity of the problem, the success of these local search algorithms depends heavily on their starting points. The most widely used initialization scheme is the spectral method, in which the leading eigenvector of a data-dependent matrix is used as a starting point. Recently, the performance of the spectral initialization was characterized accurately for measurement matrices with independent and identically distributed entries. This paper aims to obtain the same level of knowledge for isotropically random column-orthogonal matrices, which are substantially better models for practical phase retrieval systems. Towards this goal, we consider the asymptotic setting in which the number of measurements m, and the dimension of the signal, n, diverge to infinity with m/n = δ ∈ (1, ∞), and obtain a simple expression for the overlap between the spectral estimator and the true signal vector.

We study information theoretic limits of recovering an unknown n dimensional, complex signal vector x*with unit norm from m magnitude-only measurements of the form yi= |(Ax*)i|2, i = 1, 2 ..., m, where A is the sensing matrix. This is known as the Phase Retrieval problem and models practical imaging systems where measuring the phase of the observations is difficult. Since in a number of applications, the sensing matrix has orthogonal columns, we model the sensing matrix as a subsampled Haar matrix formed by picking n columns of a uniformly random m X m unitary matrix. We study this problem in the high dimensional asymptotic regime, where m, n → ∞, while m/n → δ with δ being a fixed number, and show that if mn(1)) · n, then any estimator is asymptotically orthogonal to the true signal vector x*. This lower bound is sharp since when m > (2 + on(1)) · n, estimators that achieve a non trivial asymptotic correlation with the signal vector are known from previous works.

We consider an ℓ2-regularized non-convex optimization problem for recovering signals from their noisy phaseless observations. We design and study the performance of a message passing algorithm that aims to solve this optimization problem. We consider the asymptotic setting m, n → ∞, m/n → δ and obtain sharp performance bounds, where m is the number of measurements and n is the signal dimension. We show that for complex signals, the algorithm can perform accurate recovery with only m = ((64/π2) - 4)n ≈ 2.5n measurements. Also, we provide a sharp analysis on the sensitivity of the algorithm to noise. We highlight the following facts about our message passing algorithm: 1) adding ℓ2regularization to the non-convex loss function can be beneficial and 2) spectral initialization has a marginal impact on the performance of the algorithm. The sharp analyses, in this paper, not only enable us to compare the performance of our method with other phase recovery schemes but also shed light on designing better iterative algorithms for other non-convex optimization problems.

We consider an $\ell_2$-regularized non-convex optimization problem for recovering signals from their noisy phaseless observations. We design and study the performance of a message passing algorithm that aims to solve this optimization problem. We consider the asymptotic setting $m,n \rightarrow \infty$, $m/n \rightarrow \delta$ and obtain sharp performance bounds, where $m$ is the number of measurements and $n$ is the signal dimension. We show that for complex signals the algorithm can perform accurate recovery with only $m=\left ( \frac{64}{\pi^2}-4\right)n\approx 2.5n$ measurements. Also, we provide sharp analysis on the sensitivity of the algorithm to noise. We highlight the following facts about our message passing algorithm: (i) Adding $\ell_2$ regularization to the non-convex loss function can be beneficial even in the noiseless setting; (ii) spectral initialization has marginal impact on the performance of the algorithm.

We study the parameter tuning problem for the penalized regression model. Finding the optimal choice of the regularization parameter is a challenging problem in high-dimensional regimes where both the number of observations n and the number of parameters p are large. We propose two frameworks to obtain a computationally efficient approximation ALO of the leave-one-out cross validation (LOOCV) risk for nonsmooth losses and regularizers. Our two frameworks are based on the primal and dual formulations of the penalized regression model. We prove the equivalence of the two approaches under smoothness conditions. This equivalence enables us to justify the accuracy of both methods under such conditions. We use our approaches to obtain a risk estimate for several standard problems, including generalized LASSO, nuclear norm regularization and support vector machines. We experimentally demonstrate the effectiveness of our results for non-differentiable cases.

Compressive phase retrieval is the problem of recovering a structured vector x ∈ ℂnfrom its phaseless linear measurements. A compression algorithm aims to represent structured signals with as few bits as possible. As a result of extensive research devoted to compression algorithms, in many signal classes, compression algorithms are capable of employing sophisticated structures in signals and compress them efficiently. This raises the following important question: Can a compression algorithm be used to solve a compressive phase retrieval problem? To address this question, COmpressive PhasE Retrieval (COPER) optimization is proposed, which is a compression-based phase retrieval method. For a family of compression codes with rate-distortion function denoted by r(δ), in the noiseless setting, COPER is shown to require slightly more than limδ→0(r(δ))/(log (1/δ)) observations for an almost accurate recovery of x.

Expectation Maximization (EM) is among the most popular algorithms for maximum likelihood estimation, but it is generally only guaranteed to find its stationary points of the log-likelihood objective. The goal of this article is to present theoretical and empirical evidence that over-parameterization can help EM avoid spurious local optima in the log-likelihood. We consider the problem of estimating the mean vectors of a Gaussian mixture model in a scenario where the mixing weights are known. Our study shows that the global behavior of EM, when one uses an over-parameterized model in which the mixing weights are treated as unknown, is better than that when one uses the (correct) model with the mixing weights fixed to the known values. For symmetric Gaussians mixtures with two components, we prove that introducing the (statistically redundant) weight parameters enables EM to find the global maximizer of the log-likelihood starting from almost any initial mean parameters, whereas EM without this over-parameterization may very often fail. For other Gaussian mixtures, we provide empirical evidence that shows similar behavior. Our results corroborate the value of over-parameterization in solving non-convex optimization problems, previously observed in other domains.

A novel low-complexity robust-to-noise iterative algorithm named compression-based gradient descent (C-GD) algorithm is proposed. C-GD is a generic compressed sensing recovery algorithm, that at its core, employs compression codes, such as JPEG2000 and MPEG4. Through using compression codes, C-GD strongly generalizes the scope of structures used by compressed sensing recovery algorithms beyond sparsity or low-rankness. The squared error of the proposed method and its associated convergence is characterized and predicts the strong performance of C-GD. Numerical results suggest that C-GD, when combined with state-of-the-art compression codes, either outperforms or performs comparably to modern compressed sensing recovery methods.

This paper deals with linear equalization in massive multi-user multiple-input multiple-output (MU-MIMO) wireless systems. We first provide simple conditions on the antenna configuration for which the well-known linear minimum mean-square error (L-MMSE) equalizer provides near-optimal spectral efficiency, and we analyze its performance in the presence of parameter mismatches in the signal and/or noise powers. We then propose a novel, optimally-tuned NOnParametric Equalizer (NOPE) for massive MU-MIMO systems, which avoids knowledge of the transmit signal and noise powers altogether. We show that NOPE achieves the same performance as that of the L-MMSE equalizer in the large-antenna limit, and we demonstrate its efficacy in realistic, finite-dimensional systems. From a practical perspective, NOPE is computationally efficient and avoids dedicated training that is typically required for parameter estimation.

In many application areas ranging from bioinformatics to imaging, we are faced with the following question: can we recover a sparse vector xo∈ ℝNfrom its undersampled set of noisy observations y ∈ ℝn, y = Axo+w. The last decade has witnessed a surge of algorithms and theoretical results to address this question. One of the most popular schemes is the ℓp-regularized least squares given by the following formulation:x̂(y, p) ∈ arg minx(1/2)∥y - Ax∥22+ γ∥x∥pp, where p ∈ [0, 1]. Among these optimization problems, the case p = 1, also known as LASSO, is the best accepted in practice, for the following two reasons. First, thanks to the extensive studies performed in the fields of high-dimensional statistics and compressed sensing, we have a clear picture of LASSO's performance. Second, it is convex and efficient algorithms exist for finding its global minima. Unfortunately, neither of the above two properties hold for 0 ≤ pothan x̂(γ, 1). Second, if we employ iterative methods that aim to converge to a local minima of arg minx(1/2)∥y - Ax∥22+ γ∥x∥pp, then under good initialization, these algorithms converge to a solution that is still closer to xothan x̂(γ, 1). In spite of the existence of plenty of empirical results that support these folklore theorems, the theoretical progress to establish them has been very limited. This paper aims to study the above-mentioned folklore theorems and establish their scope of validity. Starting with approximate message passing (AMP) algorithm as a heuristic method for solving ℓp-regularized least squares, we study the following questions. First, what is the impact of initialization on the performance of the algorithm? Second, when does the algorithm recover the sparse signal xounder a “good” initialization? Third, when does the algorithm converge to the sparse signal regardless of the initialization? Studying these questions will not only shed light on the second folklore theorem, but also lead us to the answer the first one, i.e., the performance of the global optima x̂(γ, p). For that purpose, we employ the replica analysis1to show the connection between the solution of AMP and x̂(γ, p) in the asymptotic settings. This enables us to compare the accuracy of x̂(γ, p) and x̂(γ, 1). In particular, we will present an accurate characterization of the phase transition and noise sensitivity of ℓp-regularized least squares for every 0 ≤ pp-regularized least squares (if γ is tuned optimally) exhibits the same phase transition for every 0 ≤ pp-regularized least squares with different values of p. For instance, we will show that for very small and very large measurement noises, p = 0 and p = 1 outperform the other values of p, respectively.

The explosion of computational imaging has seen the frontier of image processing move past linear problems, like denoising and deblurring, and towards non-linear problems such as phase retrieval. There has a been a corresponding research thrust into non-linear image recovery algorithms, but in many ways this research is stuck where linear problem research was twenty years ago: Models, if used at all, are simple designs like sparsity or smoothness. In this paper we use denoisers to impose elaborate and accurate models in order to perform inference on generalized linear systems. More specifically, we use the state-of-the-art BM3D denoiser within the Generalized Approximate Message Passing (GAMP) framework to solve compressive phase retrieval in a variety of different contexts. Our method demonstrates recovery performance equivalent to existing techniques using fewer than half as many measurements. This dramatic improvement in compressive phase retrieval performance opens the door for a whole new class of imaging systems.

We investigate the performance of mismatched data detection in large multiple-input multiple-output (MIMO) systems, where the prior distribution of the transmit signal used in the data detector differs from the true prior. To minimize the performance loss caused by this prior mismatch, we include a tuning stage into our recently-proposed large MIMO approximate message passing (LAMA) algorithm, which allows us to develop mismatched LAMA algorithms with optimal as well as sub-optimal tuning. We show that carefully-selected priors often enable simpler and computationally more efficient algorithms compared to LAMA with the true prior while achieving near-optimal performance. A performance analysis of our algorithms for a Gaussian prior and a uniform prior within a hypercube covering the QAM constellation recovers classical and recent results on linear and non-linear MIMO data detection, respectively.

Recovering a sparse vector x0∈ ℝNfrom its noisy linear observations, y ∈ ℝnwith y = Ax0+ w, has been the central problem of compressed sensing. One of the classes of recovery algorithms that has attracted attention is the class of ℓp-regularized least squares (LPLS) that seeks the minimum of 1/2 ∥y - Ax∥22+ λ∥x∥ppfor p ∈ [0, 1]. In this paper we employ the Replica method1from statistical physics to analyze the global minima of LPLS. Our paper reveals several surprising asymptotic properties of LPLS: (i) The phase transition curve of LPLS is the same for every 0 ≤ p0. (iii) Despite the equality of the phase transition curves, different values of p show different performances once a small amount of measurement noise, w, is added.

Expectation Maximization (EM) is among the most popular algorithms for estimating parameters of statistical models. However, EM, which is an iterative algorithm based on the maximum likelihood principle, is generally only guaranteed to find stationary points of the likelihood objective, and these points may be far from any maximizer. This article addresses this disconnect between the statistical principles behind EM and its algorithmic properties. Specifically, it provides a global analysis of EM for specific models in which the observations comprise an i.i.d. sample from a mixture of two Gaussians. This is achieved by (i) studying the sequence of parameters from idealized execution of EM in the infinite sample limit, and fully characterizing the limit points of the sequence in terms of the initial parameters; and then (ii) based on this convergence analysis, establishing statistical consistency (or lack thereof) for the actual sequence of parameters produced by EM.

A denoising algorithm seeks to remove noise, errors, or perturbations from a signal. Extensive research has been devoted to this arena over the last several decades, and as a result, todays denoisers can effectively remove large amounts of additive white Gaussian noise. A compressed sensing (CS) reconstruction algorithm seeks to recover a structured signal acquired using a small number of randomized measurements. Typical CS reconstruction algorithms can be cast as iteratively estimating a signal from a perturbed observation. This paper answers a natural question: How can one effectively employ a generic denoiser in a CS reconstruction algorithm? In response, we develop an extension of the approximate message passing (AMP) framework, called denoising-based AMP (D-AMP), that can integrate a wide class of denoisers within its iterations. We demonstrate that, when used with a high-performance denoiser for natural images, D-AMP offers the state-of-the-art CS recovery performance while operating tens of times faster than competing methods. We explain the exceptional performance of D-AMP by analyzing some of its theoretical features. A key element in D-AMP is the use of an appropriate Onsager correction term in its iterations, which coerces the signal perturbation at each iteration to be very close to the white Gaussian noise that denoisers are typically designed to remove.

A denoising algorithm seeks to remove perturbations or errors from a signal. The last three decades have seen extensive research devoted to this arena, and as a result, today's denoisers are highly optimized algorithms that effectively remove large amounts of additive white Gaussian noise. A compressive sensing (CS) reconstruction algorithm seeks to recover a structured signal acquired from a small number of randomized measurements. Typical CS reconstruction algorithms can be cast as iteratively estimating a signal from a perturbed observation. This paper answers a natural question: How can one effectively employ a generic denoiser in a CS reconstruction algorithm? In response, we develop a denoising-based approximate message passing (D-AMP) algorithm that is capable of high-performance reconstruction. We demonstrate using the high performance BM3D denoiser that D-AMP offers state-of-the-art CS recovery performance for natural images (on average 9dB better than sparsity-based algorithms), while operating tens of times faster than the only competitive method. A critical insight in our approach is the use of an appropriate Onsager correction term in the D-AMP iterations, which coerces the signal perturbation at each iteration to be very close to the white Gaussian noise that denoisers are typically designed to remove. On the analytical side, we develop a new state evolution framework for deterministic signals that accurately predicts the performance of D-AMP and enables us to derive several useful theoretical features.

Optimal data detection in multiple-input multiple-output (MIMO) communication systems with a large number of antennas at both ends of the wireless link entails prohibitive computational complexity. In order to reduce the computational complexity, a variety of sub-optimal detection algorithms have been proposed in the literature. In this paper, we analyze the optimality of a novel data-detection method for large MIMO systems that relies on approximate message passing (AMP). We show that our algorithm, referred to as individually-optimal (IO) large-MIMO AMP (short IO-LAMA), is able to perform IO data detection given certain conditions on the MIMO system and the constellation set (e.g., QAM or PSK) are met.

The nascent field of compressed sensing is founded on the fact that high-dimensional signals with simple structure can be recovered accurately from just a small number of randomized samples. Several specific kinds of structures have been explored in the literature, from sparsity and group sparsity to low-rankness. However, two fundamental questions have been left unanswered. What are the general abstract meanings of structure and simplicity? Do there exist universal algorithms for recovering such simple structured objects from fewer samples than their ambient dimension? In this paper, we address these two questions. Using algorithmic information theory tools such as the Kolmogorov complexity, we provide a unified definition of structure and simplicity. Leveraging this new definition, we develop and analyze an abstract algorithm for signal recovery motivated by Occam's Razor. Minimum complexity pursuit (MCP) requires approximately 2κ randomized samples to recover a signal of complexity κ and ambient dimension n. We also discuss the performance of the MCP in the presence of measurement noise and with approximately simple signals.

Can compression algorithms be employed for recovering signals from their underdetermined set of linear measurements? Addressing this question is the first step towards applying compression algorithms for compressed sensing (CS). In this paper, we consider a family of compression algorithms CR, parametrized by rate R, for a compact class of signals Q ⊂ Rn. The set of natural images and JPEG2000 at different rates are examples of Q and Cr, respectively. We establish a connection between the rate-distortion performance of CR, and the number of linear measurement required for successful recovery in CS. We then propose compressible signal pursuit (CSP) algorithm and prove that, with high probability, it accurately and robustly recovers signals from an underdetermined set of linear measurements.

Recovering a sparse signal from an undersampled set of random linear measurements is the main problem of interest in compressed sensing. In this paper, we consider the case where both the signal and the measurements are complex-valued. We study the popular recovery method ofl1-regularized least squares or LASSO. While several studies have shown that LASSO provides desirable solutions under certain conditions, the precise asymptotic performance of this algorithm in the complex setting is not yet known. In this paper, we extend the approximate message passing (AMP) algorithm to solve the complex-valued LASSO problem and obtain the complex approximate message passing algorithm (CAMP). We then generalize the state evolution framework recently introduced for the analysis of AMP to the complex setting. Using the state evolution, we derive accurate formulas for the phase transition and noise sensitivity of both LASSO and CAMP. Our theoretical results are concerned with the case of i.i.d. Gaussian sensing matrices. Simulations confirm that our results hold for a larger class of random matrices.

A host of problems involve the recovery of structured signals from a dimensionality reduced representation such as a random projection; examples include sparse signals (compressive sensing) and low-rank matrices (matrix completion). Given the wide range of different recovery algorithms developed to date, it is natural to ask whether there exist “universal” algorithms for recovering “structured” signals from their linear projections. We recently answered this question in the affirmative in the noise-free setting. In this paper, we extend our results to the case of noisy measurements.

Sparse graphical modelling/inverse covariance selection is an important problem in machine learning and has seen significant advances in recent years. A major focus has been on methods which perform model selection in high dimensions. To this end, numerous convex $\ell_1$ regularization approaches have been proposed in the literature. It is not however clear which of these methods are optimal in any well-defined sense. A major gap in this regard pertains to the rate of convergence of proposed optimization methods. To address this, an iterative thresholding algorithm for numerically solving the $\ell_1$-penalized maximum likelihood problem for sparse inverse covariance estimation is presented. The proximal gradient method considered in this paper is shown to converge at a linear rate, a result which is the first of its kind for numerically solving the sparse inverse covariance estimation problem. The convergence rate is provided in closed form, and is related to the condition number of the optimal point. Numerical results demonstrating the proven rate of convergence are presented.

The inefficiency of separable wavelets in representing smooth edges has led to a great interest in the study of new 2-D transformations. The most popular criterion for analyzing these transformations is the approximation power. Transformations with near-optimal approximation power are useful in many applications such as denoising and enhancement. However, they are not necessarily good for compression. Therefore, most of the nearly optimal transformations such as curvelets and contourlets have not found any application in image compression yet. One of the most promising schemes for image compression is the elegant idea of directional wavelets (DIWs). While these algorithms outperform the state-of-the-art image coders in practice, our theoretical understanding of them is very limited. In this paper, we adopt the notion of rate-distortion and calculate the performance of the DIW on a class of edge-like images. Our theoretical analysis shows that if the edges are not "sharp," the DIW will compress them more efficiently than the separable wavelets. It also demonstrates the inefficiency of the quadtree partitioning that is often used with the DIW. To solve this issue, we propose a new partitioning scheme called megaquad partitioning. Our simulation results on real-world images confirm the benefits of the proposed partitioning algorithm, promised by our theoretical analysis.

The inefficiency of separable wavelets in representing smooth edges has motivated the researchers to pursue new two dimensional transformations. One of the successful transformations in image compression is the directional wavelets. Although researchers have empirically shown that the directional wavelets outperform the separable wavelets in compression, there is no theoretical analysis to demonstrate this phenomena, specially when the directional wavelets are combined with partitioning algorithms such as quadtree. In this paper, we calculate the rate-distortion performance of the directional wavelets on a class of images. Our analysis shows that the quadtree partitioning deteriorates the performance. There fore we propose another scheme, called megablocking. Our theoretical and simulation results confirm that megablocking outperforms the quadtree approach.

We consider the compressed sensing problem where the object x0∈ ℝNis to be recovered from incomplete measurements y = Ax0+z. Here the sensing matrix A is an n×N random matrix with Gaussian entries and n1-penalized least-squares reconstruction (aka LASSO, Basis Pursuit). Suppose that xοis sparse in the sense of having ℓρnorm bounded by ξ · N1/ρfor some fixed 0; 0. In both the noisy (ziiid N(0, σ2)) and noiseless (z = 0) cases, we evaluate the worst-case asymptotic mean square error (AMSE) for optimally tuned ℓ1penalized least-squares, and we exhibit the least-favorable object xο(hardest sparse signal to recover) and the maximin penalization. Our explicit formulas yield precise relations. For example, in the noiseless case z = 0, for vectors xοof ℓρnorm bounded by 1, we show that mm max∥ x̑λ- x0∥2= n1-2/p(2log(N/n))2/p-1{1+oN(l)} where n, N → ∞, n/N → 0 slowly. The complete formulas applies to a general scaling limit n/N → δ and sparsity parameter ξ, and unexpectedly involve quantities from statistical decision theory. This reflects a deep connection between ℓ1-penalized ℓ2minimization and scalar soft thresholding.

Compressed sensing (CS) exploits the compressibility of natural signals to reduce the number of samples required for accurate reconstruction. The cost for sub-Nyquist sampling has been computationally expensive reconstruction algorithms, including large-scale ℓ1optimization. Therefore, first-order optimization methods that exploit only the gradient of the reconstruction cost function have been developed; notable examples include iterative soft thresholding (IST), fast iterative soft thresholding algorithm (FISTA), and approximate message passing (AMP). The performance of these algorithms has been studied mainly in the standard framework of convex optimization, called the deterministic framework here. In this paper, we first show that the deterministic approach results in overly pessimistic conclusions that are not indicative of algorithm performance in practice. As an alternative to the deterministic framework, we second study the theoretical aspects of the statistical convergence rate, a topic that has remained unexplored in the sparse recovery literature. Our theoretical and empirical studies reveal several hallmark properties of the statistical convergence of first-order methods, including universality over the matrix ensemble and the least favorable coefficient distribution.

Consider the noisy underdetermined system of linear equations: y = Ax0+ z, with A an n × N measurement matrix, n2I) a Gaussian white noise. Both y and A are known, both x0and z are unknown, and we seek an approximation to x0. When x0has few nonzeros, useful approximations are often obtained by ℓ1-penalized ℓ2minimization, in which the reconstruction x̂1,λsolves min{||y - Ax||22/2 + λ||x||1}. Consider the reconstruction mean-squared error MSE = E|| x̂1,λ- x0||22/N, and define the ratio MSE/σ2as the noise sensitivity. Consider matrices A with i.i.d. Gaussian entries and a large-system limit in which n, N → ∞ with n/N → δ and k/n → ρ. We develop exact expressions for the asymptotic MSE of x̂1,λ, and evaluate its worst-case noise sensitivity over all types of k-sparse signals. The phase space 0 ≤ 8, ρ ≤ 1 is partitioned by the curve ρ = ρMSE(δ) into two regions. Formal noise sensitivity is bounded throughout the region ρ = ρMSE(δ) and is unbounded throughout the region ρ = ρMSE(δ). The phase boundary ρ = ρMSE(δ) is identical to the previously known phase transition curve for equivalence of ℓ1- ℓ0minimization in the k-sparse noiseless case. Hence, a single phase boundary describes the fundamental phase transitions both for the noise less and noisy cases. Extensive computational experiments validate these predictions, including the existence of game-theoretical structures underlying it (saddlepoints in the payoff, least-favorable signals and maximin penalization). Underlying our formalism is an approximate message passing soft thresholding algorithm (AMP) introduced earlier by the authors. Other papers by the authors detail expressions for the formal MSE of AMP and its close connection to ℓ1-penalized reconstruction. The focus of the present paper is on computing the minimax formal MSE within the class of sparse signals x0.

Most of the signals in nature are piecewise smooth. One of the simple and yet efficient models for representing smooth signals is the class of piecewise polynomials. In this paper compression of this class of functions is considered. Some bounds are derived for the epsiv-entropy of this class of functions. These bounds show us the best performance the optimum compression scheme can have. By comparing it with the performance of traditional binary trees, it is demonstrated that the rate- distortion behavior of binary tree is far from optimum. We will then show that a simple modification of binary trees results in much better performance binary tree algorithms. This modification will retain all the advantages of binary trees.

In this paper, we present a new framework to compress the geometry of images. This framework generalizes the standard quad partitioning approaches in compression of image geometry (e.g. wedgelet) in two ways. First, we employ an adaptive rectangular partitioning rather than quadratic partitioning. Second, our coder uses an overcomplete collection of (stripe-like) atoms which contains wedgelets as a special case. We present an information-theoretical analysis based on Kolmogorov's e- entropy to show that this collection provides a near-optimal representation of a class of cartoon images with piecewise polynomial boundaries. Furthermore, we develop a provably near-optimal greedy algorithm that significantly reduces the complexity of the exhaustive search method required to achieve the entropy bound. Simulation results for the rate distortion shows a 1.5-2 dB improvement over the standard wedgelets for the "Cameraman" image.

We introduce a class of geodesic distances and extend the K-means clustering algorithm to employ this distance metric. Empirically, we demonstrate that our geodesic K-means algorithm exhibits several desirable characteristics missing in the classical K-means. These include adjusting to varying densities of clusters, high levels of resistance to outliers, and handling clusters that are not linearly separable. Furthermore our comparative experiments show that geodesic K-means comes very close to competing with state-of-the-art algorithms such as spectral and hierarchical clustering.

We propose a novel adaptive wavelet transform that exploits local image properties for image compression. It combines wavelet filters adaptive to edge orientations with quincunx subsampling to form a 2-D nonseparable transform through lifting. Filter selections are efficiently represented. Significant improvement on both subjective and objective quality over the conventional separable transform is observed. In addition, unlike previous adaptive transforms, the symmetry in quincunx subsampling enables even quality for image features along different directions and the compression performance is insensitive to image orientation