Recent works exploring the training dynamics of homogeneous neural network weights under gradient flow with small initialization have established that in the early stages of training, the weights remain small and near the origin, but converge in direction. Building on this, the current paper studies the gradient flow dynamics of homogeneous neural networks with locally Lipschitz gradients, after they escape the origin. Insights gained from this analysis are used to characterize the first saddle point encountered by gradient flow after escaping the origin. Also, it is shown that for homogeneous feed-forward neural networks, under certain conditions, the sparsity structure emerging among the weights before the escape is preserved after escaping the origin and until reaching the next saddle point.

Model-based reconstruction methods have emerged as a powerful alternative to classical Fourier-based MRI techniques, largely because of their ability to explicitly model (and therefore, potentially overcome) moderate field inhomogeneities, streamline reconstruction from non-Cartesian sampling, and even allow for the use of custom designed non-Fourier encoding methods. Their application in such scenarios, however, often comes with a substantial increase in computational cost, owing to the fact that the corresponding forward model in such settings no longer possesses a direct Fourier Transform based implementation. This paper introduces an algorithmic framework designed to reduce the computational burden associated with model-based MRI reconstruction tasks. The key innovation is the strategic sparsification of the corresponding forward operators for these models, giving rise to approximations of the forward models (and their adjoints) that admit low computational complexity application. This enables overall a reduced computational complexity application of popular iterative first-order reconstruction methods for these reconstruction tasks. Computational results obtained on both synthetic and experimental data illustrate the viability and efficiency of the approach.

We consider the problem of factorizing a structured 3-way tensor into its constituent Canonical Polyadic (CP) factors. This decomposition, which can be viewed as a generalization of singular value decomposition (SVD) for tensors, reveals how the tensor dimensions (features) interact with each other. However, since the factors are a priori unknown, the corresponding optimization problems are inherently non-convex. The existing guaranteed algorithms which handle this non-convexity incur an irreducible error (bias), and only apply to cases where all factors have the same structure. To this end, we develop a provable algorithm for online structured tensor factorization, wherein one of the factors obeys some incoherence conditions, and the others are sparse. Specifically we show that, under some relatively mild conditions on initialization, rank, and sparsity, our algorithm recovers the factors exactly (up to scaling and permutation) at a linear rate. Complementary to our theoretical results, our synthetic and real-world data evaluations showcase superior performance compared to related techniques.

This work examines the problem of exact data interpolation via sparse (neuron count), infinitely wide, single hidden layer neural networks with leaky rectified linear unit activations. Using the atomic norm framework of [Chandrasekaran et al. 2012], we derive simple characterizations of the convex hulls of the corresponding atomic sets for this problem under several different constraints on the weights and biases of the network, thus obtaining equivalent convex formulations for these problems. A modest extension of our proposed framework to a binary classification problem is also presented. We explore the efficacy of the resulting formulations experimentally, and compare with networks trained via gradient descent.

We study constrained nonconvex optimization problems in machine learning and signal processing. It is well-known that these problems can be rewritten to a min-max problem in a Lagrangian form. However, due to the lack of convexity, their landscape is not well understood and how to find the stable equilibria of the Lagrangian function is still unknown. To bridge the gap, we study the landscape of the Lagrangian function. Further, we define a special class of Lagrangian functions. They enjoy the following two properties: 1. Equilibria are either stable or unstable (Formal definition in Section 2); 2.Stable equilibria correspond to the global optima of the original problem. We show that a generalized eigenvalue (GEV) problem, including canonical correlation analysis and other problems as special examples, belongs to the class. Specifically, we characterize its stable and unstable equilibria by leveraging an invariant group and symmetric property (more details in Section 3). Motivated by these neat geometric structures, we propose a simple, efficient, and stochastic primal-dual algorithm solving the online GEV problem. Theoretically, under sufficient conditions, we establish an asymptotic rate of convergence and obtain the first sample complexity result for the online GEV problem by diffusion approximations, which are widely used in applied probability. Numerical results are also provided to support our theory.

We propose a general theory for studying the landscape of nonconvex optimization with underlying symmetric structures for a class of machine learning problems (e.g., low-rank matrix factorization, phase retrieval, and deep linear neural networks). In particular, we characterize the locations of stationary points and the null space of Hessian matrices of the objective function via the lens of invariant groups. As a major motivating example, we apply the proposed general theory to characterize the global landscape of the nonconvex optimization in low-rank matrix factorization problem. We illustrate how the rotational symmetry group gives rise to infinitely many nonisolated strict saddle points and equivalent global minima of the objective function. By explicitly identifying all stationary points, we divide the entire parameter space into three regions: (R1) the region containing the neighborhoods of all strict saddle points where the objective has negative curvature; (R2) the region containing neighborhoods of all global minima, where the objective enjoys strong convexity along certain directions; and (R3) the complement of the above regions, where the gradient has sufficiently large magnitude. We further extend our result to the matrix sensing problem. Such global landscape implies that strong global convergence guarantees for popular iterative algorithms with arbitrary initial solutions.

In this paper, we examine the problem of locating vector outliers from a large number of inliers, with a particular focus on the case where the outliers are represented in a known basis or dictionary. Using a convex demixing formulation, we provide provable guarantees for exact recovery of the space spanned by the inliers and the supports of the outlier columns, even when the rank of inliers is high and the number of outliers is a constant proportion of total observations. Comprehensive numerical experiments on both synthetic and hyper-spectral imaging real datasets demonstrate the efficiency of our proposed method.

This paper examines fundamental error characteristics for a general class of matrix completion problems, where the matrix of interest is a product of two a priori unknown matrices, one of which is sparse, and the observations are noisy. Our main contributions come in the form of minimax lower bounds for the expected per-element squared error for this problem under several common noise models. Specifically, we analyze scenarios where the corruptions are characterized by additive Gaussian noise or additive heavier-tailed (Laplace) noise, Poisson-distributed observations, and highly-quantized (e.g., one bit) observations, as instances of our general result. Our results establish that the error bounds derived in (Soni et al., 2016) for complexity-regularized maximum likelihood estimators achieve, up to multiplicative constants and logarithmic factors, the minimax error rates in each of these noise scenarios, provided that the nominal number of observations is large enough, and the sparse factor has (on an average) at least one non-zero per column.

This paper considers the problem of estimating an unknown high dimensional signal from (typically low-dimensional) noisy linear measurements, where the desired unknown signal is assumed to possess a group-sparse structure, i.e. given a (pre-defined) partition of its entries into groups, only a small number of such groups are non-zero. Assuming the unknown group-sparse signal is generated according to a certain statistical model, we provide guarantees under which it can be efficiently estimated via solving the well-known group Lasso problem. In particular, we demonstrate that the set of indices for non-zero groups of the signal (called the group-level support of the signal) can be exactly recovered by solving the proposed group Lasso problem provided that its constituent non-zero groups are small in number and possess enough energy. Our guarantees rely on the well-conditioning of measurement matrix, which is expressed in terms of the block coherence parameter and can be efficiently computed. Our results are non-asymptotic in nature and therefore applicable to practical scenarios.

This paper examines the existence of efficiently implementable approximations of a general real linear dimensionality reduction (LDR) operator. The specific focus is on approximating a given LDR operator with a partial circulant structured matrix (a matrix whose rows are related by circular shifts) as these constructions allow for low-memory footprint and computationally efficient implementations. Our main contributions are theoretical: we quantify how well general matrices may be approximated (in a Frobenius sense) by partial circulant structured matrices, and also consider a variation of this problem where the aim is only to accurately approximate the action of a given LDR operator on a restricted set of inputs. For the latter setting, we also propose a sparsity-regularized alternating minimization based algorithm for learning partial circulant approximations from data, and provide experimental evidence demonstrating the potential efficacy of this approach on real-world data.

“To be considered for the 2017 IEEE Jack Keil Wolf ISIT Student Paper Award.” In this paper we study the problem of noisy tensor completion for tensors that admit a canonical polyadic or CANDE-COMP/PARAFAC (CP) decomposition with one of the factors being sparse. We present general theoretical error bounds for an estimate obtained by using a complexity-regularized maximum likelihood principle and then instantiate these bounds for the case of additive white Gaussian noise. We also provide an ADMM-type algorithm for solving the complexity-regularized maximum likelihood problem and validate the theoretical finding via experiments on synthetic data set.

We study the least squares regression problem $\min_{\Theta \in \RR^{p_1 \times \cdots \times p_D}} \| \cA(\Theta) - b \|_2^2$, where $\Theta$ is a low-rank tensor, defined as $\Theta = \sum_{r=1}^{R} \theta_1^{(r)} \circ \cdots \circ \theta_D^{(r)}$, for vectors $\theta_d^{(r)} \in \mathbb{R}^{p_d}$ for all $r \in [R]$ and $d \in [D]$. %$R$ is small compared with $p_1,\ldots,p_D$, Here, $\circ$ denotes the outer product of vectors, and $\cA(\Theta)$ is a linear function on $\Theta$. This problem is motivated by the fact that the number of parameters in $\Theta$ is only $R \cdot \sum_{d=1}^D p_D$, which is significantly smaller than the $\prod_{d=1}^{D} p_d$ number of parameters in ordinary least squares regression. We consider the above CP decomposition model of tensors $\Theta$, as well as the Tucker decomposition. For both models we show how to apply data dimensionality reduction techniques based on {\it sparse} random projections $\Phi \in \RR^{m \times n}$, with $m \ll n$, to reduce the problem to a much smaller problem $\min_{\Theta} \|\Phi \cA(\Theta) - \Phi b\|_2^2$, for which $\|\Phi \cA(\Theta) - \Phi b\|_2^2 = (1 \pm \varepsilon) \| \cA(\Theta) - b \|_2^2$ holds simultaneously for all $\Theta$. We obtain a significantly smaller dimension and sparsity in the randomized linear mapping $\Phi$ than is possible for ordinary least squares regression. Finally, we give a number of numerical simulations supporting our theory.

We propose a DC proximal Newton algorithm for solving nonconvex regularized sparse learning problems in high dimensions. Our proposed algorithm integrates the proximal newton algorithm with multi-stage convex relaxation based on the difference of convex (DC) programming, and enjoys both strong computational and statistical guarantees. Specifically, by leveraging a sophisticated characterization of sparse modeling structures (i.e., local restricted strong convexity and Hessian smoothness), we prove that within each stage of convex relaxation, our proposed algorithm achieves (local) quadratic convergence, and eventually obtains a sparse approximate local optimum with optimal statistical properties after only a few convex relaxations. Numerical experiments are provided to support our theory.

We propose a stochastic variance reduced optimization algorithm for solving a class of large-scale nonconvex optimization problems with cardinality constraints, and provide sufficient conditions under which the proposed algorithm enjoys strong linear convergence guarantees and optimal estimation accuracy in high dimensions. Numerical experiments demonstrate the efficiency of our method in terms of both parameter estimation and computational performance.

This paper examines a general class of noisy matrix completion tasks, where the goal is to estimate a matrix from observations obtained at a subset of its entries, each of which is subject to random noise or corruption. Our specific focus is on settings where the matrix to be estimated is well-approximated by a product of two (a priori unknown) matrices, one of which is sparse. Such structural models-referred to here as sparse factor models-have been widely used, for example, in subspace clustering applications, as well as in contemporary sparse modeling and dictionary learning tasks. Our main theoretical contributions are estimation error bounds for sparsity-regularized maximum likelihood estimators for the problems of this form, which are applicable to a number of different observation noise or corruption models. Several specific implications are examined, including scenarios where observations are corrupted by additive Gaussian noise or additive heavier-tailed (Laplace) noise, Poisson-distributed observations, and highly quantized (e.g., 1 b) observations. We also propose a simple algorithmic approach based on the alternating direction method of multipliers for these tasks, and provide experimental evidence to support our error analyses.

We study the problem of actively learning a multi-index function of the form f(x) = g0(A0x) from its point evaluations, where A0∈ ℝk×dwith k ≫ d. We build on the assumptions and techniques of an existing approach based on low-rank matrix recovery (Tyagi and Cevher, 2012). Specifically, by introducing an additional self- concordant like assumption on g0 and adapting the sampling scheme and its analysis accordingly, we provide a bound on the sampling complexity with a weaker dependence on d in the presence of additive Gaussian sampling noise. For example, under natural assumptions on certain other parameters, the dependence decreases from O(d3/2) to O(d¾).

This paper examines the problem of locating outlier columns in a large, otherwise low-rank, matrix. We propose a simple two-step adaptive sensing and inference approach and establish theoretical guarantees for its performance. Our results show that accurate outlier identification is achievable using very few linear summaries of the original data matrix - as few as the squared rank of the low-rank component plus the number of outliers, times constant and logarithmic factors. We demonstrate the performance of our approach experimentally in two stylized applications, one motivated by robust collaborative filtering tasks, and the other by saliency map estimation tasks arising in computer vision and automated surveillance.

This work examines a sparse dictionary learning task - that of fitting a collection of data points, arranged as columns of a matrix, to a union of low-dimensional linear subspaces - in settings where only highly quantized (single bit) observations of the data matrix entries are available. We analyze a complexity penalized maximum likelihood estimation strategy, and obtain finite-sample bounds for the average per-element squared approximation error of the estimate produced by our approach. Our results are reminiscent of traditional parametric estimation tasks - we show here that despite the highly-quantized observations, the normalized per-element estimation error is bounded by the ratio between the number of “degrees of freedom” of the matrix and its dimension.

Many machine learning applications employ a multiclass classification stage that uses multiple binary linear classifiers as building blocks. Among these, commonly used strategies such as one-vs-one classification can require learning a large number of hyperplanes, even when the number of classes to be discriminated among is modest. Further, when the data being classified is inherently high-dimensional, the storage and computational complexity associated with the application of multiple linear classifiers can ignite critical resource management issues. This work describes a novel multiclass classification method based on efficient use of a single “recycled” linear classifier (or ReLiC), which addresses these storage and implementation complexity issues. The proposed approach amounts to constraining the entire collection of hyperplanes to be circularly-shifted versions of each other, enabling classification procedures that may be implemented with efficient operations, such as circular convolution (which can be efficiently computed using transform domain techniques), and simple sampling/thresholding operations. We show that the optimization task associated with our proposed approach can be formulated as a quadratic program, and we introduce an efficient distributed procedure for its solution based on an alternating direction method of multipliers. Simulation results demonstrate that the performance of the proposed approach is comparable with the more complex, traditional multiclass linear classification strategies, suggesting the proposed approach is a viable alternative in large-scale data classification tasks.

Poisson processes are commonly used models for describing discrete arrival phenomena arising, for example, in photon-limited scenarios in low-light and infrared imaging, astronomy, and nuclear medicine applications. In this context, several recent efforts have evaluated Poisson denoising methods that utilize contemporary sparse modeling and dictionary learning techniques designed to exploit and leverage (local) shared structure in the images being estimated. This paper establishes a theoretical foundation for such procedures. Specifically, we formulate sparse and structured dictionary-based Poisson denoising methods as constrained maximum likelihood estimation strategies, and establish performance bounds for their mean-square estimation error using the framework of complexity penalized maximum likelihood analyses.

Recent breakthrough results in compressive sensing (CS) have established that many high dimensional signals can be accurately recovered from a relatively small number of non-adaptive linear observations, provided that the signals possess a sparse representation in some basis. Subsequent efforts have shown that the performance of CS can be improved by exploiting additional structure in the locations of the nonzero signal coefficients during inference or by utilizing some form of data-dependent adaptive measurement focusing during the sensing process. To the best of our knowledge, our own previous work was the first to establish the potential benefits that can be achieved when fusing the notions of adaptive sensing and structured sparsity. In that work, we examined the task of support recovery from noisy linear measurements, and established that an adaptive sensing strategy specifically tailored to signals that are tree-sparse can significantly outperform adaptive and non-adaptive sensing strategies that are agnostic to the underlying structure. In this paper, we establish fundamental performance limits for the task of support recovery of tree-sparse signals from noisy measurements, in settings where measurements may be obtained either non-adaptively (using a randomized Gaussian measurement strategy motivated by initial CS investigations) or by any adaptive sensing strategy. Our main results here imply that the adaptive tree sensing procedure analyzed in our previous work is nearly optimal, in the sense that no other sensing and estimation strategy can perform fundamentally better for identifying the support of tree-sparse signals.

Breakthrough results in compressive sensing (CS) have shown that high dimensional signals (vectors) can often be accurately recovered from a relatively small number of non-adaptive linear projection observations, provided that they possess a sparse representation in some basis. Subsequent efforts have established that the reconstruction performance of CS can be improved by employing additional prior signal knowledge, such as dependency in the location of the non-zero signal coefficients (structured sparsity) or by collecting measurements sequentially and adaptively, in order to focus measurements into the proper subspace where the unknown signal resides. In this paper, we examine a powerful hybrid of adaptivity and structure. We identify a particular form of structured sparsity that is amenable to adaptive sensing, and using concepts from sparse hierarchical dictionary learning we demonstrate that sparsifying dictionaries exhibiting the appropriate form of structured sparsity can be learned from a collection of training data. The combination of these techniques (structured dictionary learning and adaptive sensing) results in an effective and efficient adaptive compressive acquisition approach which we refer to as LASeR (Learning Adaptive Sensing Representations).

Estimating the level set of a signal from measurements is a task that arises in a variety of fields, including medical imaging, astronomy, and digital elevation mapping. Motivated by scenarios where accurate and complete measurements of the signal may not available, we examine here a simple procedure for estimating the level set of a signal from highly incomplete measurements, which may additionally be corrupted by additive noise. The proposed procedure is based on box-constrained Total Variation (TV) regularization. We demonstrate the performance of our approach, relative to existing state-of-the-art techniques for level set estimation from compressive measurements, via several simulation examples.

Adaptive sampling results in significant improvements in the recovery of sparse signals in white Gaussian noise. A sequential adaptive sampling-and-refinement procedure called Distilled Sensing (DS) is proposed and analyzed. DS is a form of multistage experimental design and testing. Because of the adaptive nature of the data collection, DS can detect and localize far weaker signals than possible from non-adaptive measurements. In particular, reliable detection and localization (support estimation) using non-adaptive samples is possible only if the signal amplitudes grow logarithmically with the problem dimension. Here it is shown that using adaptive sampling, reliable detection is possible provided the amplitude exceeds a constant, and localization is possible when the amplitude exceeds any arbitrarily slowly growing function of the dimension.

It is shown here that adaptivity in sampling results in dramatic improvements in the recovery of sparse signals in white Gaussian noise. An adaptive sampling-and-refinement procedure called distilled sensing is discussed and analyzed, resulting in fundamental new asymptotic scaling relationships in terms of the minimum feature strength required for reliable signal detection or localization (support recovery). In particular, reliable detection and localization using non-adaptive samples is possible only if the feature strength grows logarithmically in the problem dimension. Here it is shown that using adaptive sampling, reliable detection is possible provided the feature strength exceeds a constant, and localization is possible when the feature strength exceeds any (arbitrarily slowly) growing function of the problem dimension.

High-rate data communication over a multipath wireless channel often requires that the channel response be known at the receiver. Training-based methods, which probe the channel in time, frequency, and space with known signals and reconstruct the channel response from the output signals, are most commonly used to accomplish this task. Traditional training-based channel estimation methods, typically comprising linear reconstruction techniques, are known to be optimal for rich multipath channels. However, physical arguments and growing experimental evidence suggest that many wireless channels encountered in practice tend to exhibit a sparse multipath structure that gets pronounced as the signal space dimension gets large (e.g., due to large bandwidth or large number of antennas). In this paper, we formalize the notion of multipath sparsity and present a new approach to estimating sparse (or effectively sparse) multipath channels that is based on some of the recent advances in the theory of compressed sensing. In particular, it is shown in the paper that the proposed approach, which is termed as compressed channel sensing (CCS), can potentially achieve a target reconstruction error using far less energy and, in many instances, latency and bandwidth than that dictated by the traditional least-squares-based training methods.

Compressed sensing (CS) has recently emerged as a powerful signal acquisition paradigm. In essence, CS enables the recovery of high-dimensional sparse signals from relatively few linear observations in the form of projections onto a collection of test vectors. Existing results show that if the entries of the test vectors are independent realizations of certain zero-mean random variables, then with high probability the unknown signals can be recovered by solving a tractable convex optimization. This work extends CS theory to settings where the entries of the test vectors exhibit structured statistical dependencies. It follows that CS can be effectively utilized in linear, time-invariant system identification problems provided the impulse response of the system is (approximately or exactly) sparse. An immediate application is in wireless multipath channel estimation. It is shown here that time-domain probing of a multipath channel with a random binary sequence, along with utilization of CS reconstruction techniques, can provide significant improvements in estimation accuracy compared to traditional least-squares based linear channel estimation strategies. Abstract extensions of the main results are also discussed, where the theory of equitable graph coloring is employed to establish the utility of CS in settings where the test vectors exhibit more general statistical dependencies.

The theory of compressed sensing shows that samples in the form of random projections are optimal for recovering sparse signals in high-dimensional spaces (i.e., finding needles in haystacks), provided the measurements are noiseless. However, noise is almost always present in applications, and compressed sensing suffers from it. The signal to noise ratio per dimension using random projections is very poor, since sensing energy is equally distributed over all dimensions. Consequently, the ability of compressed sensing to locate sparse components degrades significantly as noise increases. It is possible, in principle, to improve performance by "shaping" the projections to focus sensing energy in proper dimensions. The main question addressed here is, can projections be adaptively shaped to achieve this focusing effect? The answer is yes, and we demonstrate a simple, computationally efficient procedure that does so.

Compressive sampling (CS) refers to a generalized sampling paradigm in which observations are inner products between an unknown signal vector and user-specified test vectors. Among the attractive features of CS is the ability to reconstruct any sparse (or nearly sparse) signal from a relatively small number of samples, even when the observations are corrupted by additive noise. However, the potential of CS in other signal processing applications is still not fully known. This paper examines the performance of CS for the problem of signal detection. A generalized restricted isometry property (GRIP) is introduced, which guarantees that angles are preserved, in addition to the usual norm preservation, by CS. The GRIP is leveraged to derive error bounds for a CS matched filtering scheme, and to show that the scheme is robust to signal mismatch.

Power and bandwidth are scarce resources in dense wireless sensor networks and it is widely recognized that joint optimization of the operations of sensing, processing and communication can result in significant savings in the use of network resources. In this paper, a distributed joint source-channel communication architecture is proposed for energy-efficient estimation of sensor field data at a distant destination and the corresponding relationships between power, distortion, and latency are analyzed as a function of number of sensor nodes. The approach is applicable to a broad class of sensed signal fields and is based on distributed computation of appropriately chosen projections of sensor data at the destination - phase-coherent transmissions from the sensor nodes enable exploitation of the distributed beamforming gain for energy efficiency. Random projections are used when little or no prior knowledge is available about the signal field. Distinct features of the proposed scheme include: (1) processing and communication are combined into one distributed projection operation; (2) it virtually eliminates the need for in-network processing and communication; (3) given sufficient prior knowledge about the sensed data, consistent estimation is possible with increasing sensor density even with vanishing total network power; and (4) consistent signal estimation is possible with power and latency requirements growing at most sublinearly with the number of sensor nodes even when little or no prior knowledge about the sensed data is assumed at the sensor nodes.

The essential task in nearly all applications of sensor networks is to extract relevant information about the sensed data and deliver it to a desired destination. The overall goal in the design of sensor networks is to execute this task with least consumption of network resources. In this regard, the relevant metrics of interest are 1) the latency (bandwidth) involved in network data acquisition; and 2) the energy-distortion (E-D) tradeoff: given some desired distortion level D, how much energy E does the sensor network consume in extracting and delivering relevant information up to distortion D at a (usually) distant destination. It is generally recognized that given sufficient prior knowledge about the sensed data, there exist distributed processing and communication schemes that have a very favorable E-D tradeoff in the sense that D darr 0 as n rarr infin while E grows at most sub-linearly with the number of nodes (n) in the network. However, it is not known whether such schemes exist when little or no prior knowledge about the sensed data is available. In this paper, we present a distributed matched-source channel communication scheme that naturally integrates the operations of processing and communications in a sensor network and is universal in the sense that it provides us with a consistent estimation scheme such that E grows sub-linearly with n even when little prior knowledge about the sensed data is assumed. This universality, however, comes at the price of increased latency (bandwidth) and a less favorable ED tradeoff and we quantify this price by comparing our scheme to the case when sufficient prior information about the sensed data is available

Compressive sampling (CS), or Compressed Sensing, has generated a tremendous amount of excitement in the signal processing community. Compressive sampling, which involves non-traditional samples in the form of randomized projections, can capture most of the salient information in a signal with a relatively small number of samples, often far fewer samples than required using traditional sampling schemes. Adaptive sampling (AS), also called Active Learning, uses information gleaned from previous observations (e.g., feedback) to focus the sampling process. Theoretical and experimental results have shown that adaptive sampling can dramatically outperform conventional (non-adaptive) sampling schemes. This paper compares the theoretical performance of compressive and adaptive sampling in noisy conditions, and it is shown that for certain classes of piecewise constant signals and high SNR regimes both CS and AS are near-optimal. This result is remarkable since it is the first evidence that shows that compressive sampling, which is non-adaptive, cannot be significantly outperformed by any other method (including adaptive sampling procedures), even in presence of noise.

Compressive sampling (CS), or "compressed sensing," has recently generated a tremendous amount of excitement in the image processing community. CS involves taking a relatively small number of non-traditional samples in the form of randomized projections that are capable of capturing the most salient information in an image. If the image being sampled is compressible in a certain basis (e.g., wavelet), then under noiseless conditions the image can be much more accurately recovered from random projections than from pixel samples. However, the performance of CS can degrade markedly in the presence of noise. In this paper, we compare CS to conventional imaging by considering a canonical class of piecewise smooth image models. Our conclusion is that CS can be advantageous in noisy imaging problems if the underlying image is highly compressible or if the SNR is sufficiently large.

Compressive Sampling is an emerging theory that is based on the fact that a relatively small number of random projections of a signal can contain most of its salient information. In this paper, we introduce the concept of Compressive Wireless Sensing for sensor networks in which a fusion center retrieves signal field information from an ensemble of spatially distributed sensor nodes. Energy and bandwidth are scarce resources in sensor networks and the relevant metrics of interest in our context are 1) the latency involved in information retrieval; and 2) the associated power-distortion trade-off. It is generally recognized that given sufficient prior knowledge about the sensed data (e.g., statistical characterization, homogeneity etc.), there exist schemes that have very favorable power-distortion-latency trade-offs. We propose a distributed matched source-channel communication scheme, based in part on recent results in compressive sampling theory, for estimation of sensed data at the fusion center and analyze, as a function of number of sensor nodes, the trade-offs between power, distortion and latency. Compressive wireless sensing is a universal scheme in the sense that it requires no prior knowledge about the sensed data. This universality, however, comes at the cost of optimality (in terms of a less favorable power-distortion-latency trade-off) and we quantify this cost relative to the case when sufficient prior information about the sensed data is assumed.

Developing energy efficient strategies for the extraction, transmission, and dissemination of information is a core theme in wireless sensor network research. In this paper we present a novel system for decentralized data compression and predistribution. The system simultaneously computes random projections of the sensor data and disseminates them throughout the network using a simple gossiping algorithm. These summary statistics are stored in an efficient manner and can be extracted from a small subset of nodes anywhere in the network. From these measurements one can reconstruct an accurate approximation of the data at all nodes in the network, provided the original data is compressible in a certain sense which need not be known to the nodes ahead of time. The system provides a practical and universal approach to decentralized compression and content distribution in wireless sensor networks. Two example applications, network health monitoring and field estimation, demonstrate the utility of our method.

Recent results show that a relatively small number of random projections of a signal can contain most of its salient information. It follows that if a signal is compressible in some orthonormal basis, then a very accurate reconstruction can be obtained from random projections. This "compressive sampling" approach is extended here to show that signals can be accurately recovered from random projections contaminated with noise. A practical iterative algorithm for signal reconstruction is proposed, and potential applications to coding, analog-digital (A/D) conversion, and remote wireless sensing are discussed