Biomedical imaging systems often produce multidimensional signals (tensors). The high expense of image acquisition limits sample sizes and privacy regulations can prevent centralizing data from multiple sites. Federated learning can allow researchers to form research consortia to perform joint analyses without centralizing data. Standard analysis approaches for tensors often vectorize the data, resulting in high dimensional models for which the total sample size across a consortium may be insufficient. We propose a federated algorithm for tensor regression using generalized linear models (GLMs) based on a recently proposed centralized method using low separation rank (LSR) tensor decompositions. Our results show that by balancing the ratio of local update steps to rounds of communication, we can achieve results similar to those of a centralized algorithm using the entire data.

Federated learning is a technique that allows multiple entities to collaboratively train models using their data without compromising data privacy. However, despite its advantages, federated learning can be susceptible to false data injection attacks. In these scenarios, a malicious entity with control over specific agents in the network can manipulate the learning process, leading to a suboptimal model. Consequently, addressing these data injection attacks presents a significant research challenge in federated learning systems. In this paper, we propose a novel approach to detect and mitigate data injection attacks on federated learning systems. Our mitigation strategy is a local scheme, performed during a single instance of training by the coordinating node, allowing for mitigation during the convergence of the algorithm. Whenever an agent is suspected of being an attacker, its data will be ignored for a certain period; this decision will often be re-evaluated. We prove that with probability one, after a finite time, all attackers will be ignored while the probability of ignoring a trustful agent becomes zero, provided that there is a majority of truthful agents. Simulations show that when the coordinating node detects and isolates all the attackers, the model recovers and converges to the truthful model.

Gradient-related first-order methods have become the workhorse of large-scale numerical optimization problems. Many of these problems involve nonconvex objective functions with multiple saddle points, which necessitates an understanding of the behavior of discrete trajectories of first-order methods within the geometrical landscape of these functions. This paper concerns convergence of first-order discrete methods to a local minimum of nonconvex optimization problems that comprise strict-saddle points within the geometrical landscape. To this end, it focuses on analysis of discrete gradient trajectories around saddle neighborhoods, derives sufficient conditions under which these trajectories can escape strict-saddle neighborhoods in linear time, explores the contractive and expansive dynamics of these trajectories in neighborhoods of strict-saddle points that are characterized by gradients of moderate magnitude, characterizes the non-curving nature of these trajectories, and highlights the inability of these trajectories to re-enter the neighborhoods around strict-saddle points after exiting them. Based on these insights and analyses, the paper then proposes a simple variant of the vanilla gradient descent algorithm, termed Curvature Conditioned Regularized Gradient Descent (CCRGD) algorithm, which utilizes a check for an initial boundary condition to ensure its trajectories can escape strict-saddle neighborhoods in linear time. Convergence analysis of the CCRGD algorithm, which includes its rate of convergence to a local minimum, is also presented in the paper. Numerical experiments are then provided on a test function as well as a low-rank matrix factorization problem to evaluate the efficacy of the proposed algorithm.

Multi-camera networks are increasingly becoming pervasive in many monitoring and surveillance applications, and have attracted much attention in distributed systems with collaborative, real-time decision-making capabilities. While in-network data compression brings significant energy savings in camera nodes, signal representation using sparse approximations and overcomplete dictionaries have been shown to outperform traditional compression methods. In this work, an end-to-end and real-time solution is designed and implemented to enable energy-efficient and robust dictionary learning in distributed camera networks by leveraging the spatial correlation of the collected multimedia data. Traditional distributed dictionary learning relies on consensus-building algorithms, which involve communicating with neighboring nodes until convergence is achieved. Existing methods, however, do not exploit spatial correlations in camera networks for improved energy efficiency. In contrast, low-computational-complexity metrics are employed in this work to quantify and exploit the spatial correlation across camera nodes in a wireless network for efficient distributed dictionary learning and in-network image compression. The performance of the proposed approach is validated through extensive simulations on public datasets as well as via real-world experiments on a testbed composed of Raspberry Pi nodes.

Novel transmission schemes, enabled by recent advances in the fields of metamaterial (MTM), leaky-wave antenna (LWA) and directional modulation (DM), are proposed for enhancing the physical layer (PHY) security. MTM-LWAs, which offer compact, integrated, and cost-effective alternatives to the classic phased-array architectures, are particularly of interest for emerging wireless communication systems including Internet-of-Things. The proposed secure schemes are devised to accomplish the functionalities of directional modulation (DM) transmitters for orthogonal frequency-division multiplexing (OFDM) and non-contiguous OFDM transmissions, while enjoying the implementation benefits of MTM-LWAs. Specifically, transmitter architectures based on the idea of time-modulated MTM-LWA have been put forth as a promising solution for PHY security for the first time. The PHY security for the proposed schemes are investigated from the point of view of both passive and active attacks where an adversary aims to decode secret information and feed spurious data to the legitimate receiver, respectively. Numerical simulations reveal that even when the adversary employs sophisticated state-of-the-art deep learning based attacks, the proposed transmission schemes are resistant to these attacks and reliably guarantee system security.

This special issue provides a comprehensive overview of modern optimization tools and methods for the purposes of data-driven learning and control.

Emerging applications of machine learning in numerous areas-including online social networks, remote sensing, Internet-of-Things (IoT) systems, smart grids, and more-involve continuous gathering of and learning from streams of data samples. Real-time incorporation of streaming data into the learned machine learning models is essential for improved inference in these applications. Furthermore, these applications often involve data that are either inherently gathered at geographically distributed entities due to physical reasons, for example, IoT systems and smart grids, or that are intentionally distributed across multiple computing machines for memory, storage, computational, and/or privacy reasons. Training of machine learning models in this distributed, streaming setting requires solving stochastic optimization (SO) problems in a collaborative manner over communication links between the physical entities. When the streaming data rate is high compared with the processing capabilities of individual computing entities and/or the rate of the communications links, this poses a challenging question: How can one best leverage the incoming data for distributed training of machine learning models under constraints on computing capabilities and/or communications rate? A large body of research in distributed online optimization has emerged in recent decades to tackle this and related problems. This article reviews recently developed methods that focus on large-scale distributed SO in the compute- and bandwidth-limited regimes, with an emphasis on convergence analysis that explicitly accounts for the mismatch between computation, communication, and streaming rates and provides sufficient conditions for order-optimum convergence. In particular, it focuses on methods that solve: 1) distributed stochastic convex problems and 2) distributed principal component analysis, which is a nonconvex problem with the geometric structure that permits global convergence. For such methods, this article discusses recent advances in terms of distributed algorithmic designs when faced with high-rate streaming data. Furthermore, it reviews theoretical guarantees underlying these methods that show that there exist regimes in which systems can learn from distributed processing of streaming data at order-optimal rates-nearly as fast as if all the data were processed at a single superpowerful machine.

This paper focuses on principal components analysis (PCA), which involves estimating the principal subspace of a data covariance matrix, in the age of big data. Massively large datasets often require storage across multiple machines, which precludes the use of cen-tralized PCA solutions. While a number of distributed solutions to the PCA problem have been proposed recently, convergence guarantees and/or communications overhead of these solutions remain a concern. With an eye towards communications efficiency, this paper introduces two variants of a distributed PCA algorithm termed distributed Sanger's algorithm (DSA). Principal subspace estimation using both variants of DSA is communication efficient because of its one time-scale nature. In addition, theoretical guarantees are provided for the asymptotic convergence of basic DSA to the principal subspace, while its "accelerated" variant is numerically shown to have faster convergence than the state-of-the-art.

This work addresses the problem of structured dictionary learning for computing sparse representations of tensor-structured data. It introduces a low-separation-rank dictionary learning (LSR-DL) model that better captures the structure of tensor data by generalizing the separable dictionary learning model. A dictionary with p columns that is generated from the LSR-DL model is shown to be locally identifiable from noisy observations with recovery error at most ρ given that the number of training samples scales with (# of degrees of freedom in the dictionary)×p2ρ-2.

Flipped learning, in which students watch video lessons outside the class time and the instructor uses the class time for instilling of knowledge through various active learning techniques, is often put forth as a more effective mode of instruction. While a number of educators in higher education have replaced their traditional lecture-based offerings with flipped classes, it is still debatable whether flipping can be scaled up to large core classes. In this paper, experiences are recounted from two consecutive flipped offerings of a junior-level signal processing class at Rutgers with an average enrollment of 122 students. These experiences suggest that, with some improvisations, large classes can be successfully flipped with minimal time, cost, and infrastructure overhead.

This letter proposes an algorithm for clustering of two-dimensional data. Instead of “flattening” data into vectors, the proposed algorithm keeps samples as matrices and stores them as lateral slices in a third-order tensor. It is then assumed that the samples lie near a union of free submodules and their representations under this model are obtained by imposing a low tensor-rank constraint and a structural constraint on the representation tensor. Clustering is carried out using an affinity matrix calculated from the representation tensor. Effectiveness of the proposed algorithm and its superiority over existing methods are demonstrated through experiments on two image datasets.

This paper provides fundamental limits on the sample complexity of estimating dictionaries for tensor data. The specific focus of this work is on Kth-order tensor data and the case where the underlying dictionary can be expressed in terms of K smaller dictionaries. It is assumed the data are generated by linear combinations of these structured dictionary atoms and observed through white Gaussian noise. This work first provides a general lower bound on the minimax risk of dictionary learning for such tensor data and then adapts the proof techniques for specialized results in the case of sparse and sparse-Gaussian linear combinations. The results suggest the sample complexity of dictionary learning for tensor data can be significantly lower than that for unstructured data: for unstructured data it scales linearly with the product of the dictionary dimensions, whereas for tensor-structured data the bound scales linearly with the sum of the product of the dimensions of the (smaller) component dictionaries. A partial converse is provided for the case of 2nd-order tensor data to show that the bounds in this paper can be tight. This involves developing an algorithm for learning highly-structured dictionaries from noisy tensor data. Finally, numerical experiments highlight the advantages associated with explicitly accounting for tensor data structure during dictionary learning.

This paper provides bounds on the sample complexity of estimating Kronecker-structured dictionaries for Kth-order tensor data. The training samples are generated by linear combinations of these structured dictionary atoms and observed through white Gaussian noise. The lower bound follows from a lower bound on the minimax risk for general coefficient distributions and can be further specialized to sparse-Gaussian coefficients. This bound scales linearly with the sum of the product of the dimensions of the (smaller) coordinate dictionaries for tensor data. An explicit dictionary estimation algorithm for 2nd-order tensor data is also provided whose sample complexity matches the lower bound in the scaling sense. Numerical experiments highlight the advantages associated with explicitly accounting for tensor structure of data during dictionary learning.

In this paper, we propose a general framework that transforms the problems of designing sparse finite-impulse-response linear equalizers and nonlinear decision-feedback equalizers, for multiple antenna systems, into the problem of sparsest approximation of a vector in different dictionaries. In addition, we investigate several choices of the sparsifying dictionaries under this framework. Furthermore, the worst case coherences of these dictionaries, which determine their sparsifying effectiveness, are analytically and/or numerically evaluated. Moreover, we show how to reduce the computational complexity of the designed sparse equalizer filters by exploiting the asymptotic equivalence of Toeplitz and circulant matrices. Finally, the superiority of our proposed framework over conventional methods is demonstrated through numerical experiments.

Support vector machines (SVMs) are one of the most widely used supervised learning algorithms for classification problems. Recent years have witnessed an increasing interest in distributed variants of SVMs, in which the (labeled) training data is distributed across different nodes. While a number of algorithms have been developed in this regard, they all make the simplified assumption that every node in the network operates as intended. In many applications, however, it is common for some of the nodes to undergo failures due to faulty equipment, cyber attacks, etc., and inject faulty data into the network. This kind of failure, termed Byzantine failure, is impossible to protect against using existing distributed SVM algorithms. This paper revisits the problem of distributed SVM under the possibility of Byzantine failures in the network. In this regard, it proposes a novel algorithm for distributed SVM that remains resilient to Byzantine failures as long as the number of faulty nodes in the network is not too large. Numerical results on real-world data confirm the superiority of the proposed algorithm over existing approaches.

A major performance and complexity limitation in broadband communications is the long channel delay spread which results in a highly-frequency-selective channel frequency response. Channel shortening equalizers (CSEs) are used to ensure that the cascade of a long channel impulse response (CIR) and the CSE is approximately equivalent to a target impulse response (TIR) with much shorter delay spread. In this paper, we propose a general framework that transforms the problems of design of sparse CSE and TIR finite impulse response (FIR) filters into the problem of sparsest-approximation of a vector in different dictionaries. In addition, we compare several choices of sparsifying dictionaries under this framework. Furthermore, the worst-case coherence of these dictionaries, which determines their sparsifying effectiveness, are analytically and/or numerically evaluated. Finally, the usefulness of the proposed framework for the design of sparse CSE and TIR filters is validated through numerical experiments.

Dictionary learning is the problem of estimating the collection of atomic elements that provide a sparse representation of measured/collected signals or data. This paper finds fundamental limits on the sample complexity of estimating dictionaries for tensor data by proving a lower bound on the minimax risk. This lower bound depends on the dimensions of the tensor and parameters of the generative model. The focus of this paper is on second-order tensor data, with the underlying dictionaries constructed by taking the Kronecker product of two smaller dictionaries and the observed data generated by sparse linear combinations of dictionary atoms observed through white Gaussian noise. In this regard, the paper provides a general lower bound on the minimax risk and also adapts the proof techniques for equivalent results using sparse and Gaussian coefficient models. The reported results suggest that the sample complexity of dictionary learning for tensor data can be significantly lower than that for unstructured data.

We evaluated passive radio-frequency identification (RFID) technology for detecting the use of objects and related activities during trauma resuscitation. Our system consists of RFID tags and antennas, optimally placed for object detection, as well as algorithms for processing RFID data to infer object use. To evaluate our approach, we tagged 81 objects in the resuscitation room and recorded RFID signal strength during 32 simulated resuscitations performed by trauma teams. We then analyzed RFID data to identify cues for recognizing resuscitation activities. Using these cues, we extracted descriptive features and applied machine-learning techniques to monitor interactions with objects. Our results show that an instance of a used object can be detected with accuracy rates greater than 90 percent in a crowded and fast-paced medical setting using off-the-shelf RFID equipment, and the time and duration of use can be identified with up to 83 percent accuracy. We conclude with insights into the limitations of passive RFID and areas in which RFID needs to be complemented with other sensing technologies.

This paper addresses the problem of learning a collection of nonlinear manifolds. Inspired by kernel methods, it puts forth a generalization of the kernel subspace model, termed the Metric-Constrained Kernel Union-of-Subspaces (MC-KUoS) model. It then develops an iterative method for learning of an MC-KUoS whose solution is based on the data representation capability of the manifolds and distances between subspaces in the kernel (feature) space. The proposed method (when using Gaussian and polynomial kernels) outperforms existing competitive state-of-the-art methods for real-world image denoising, which shows the benefits of the MC-KUoS model and the proposed denoising approach.

This paper provides a convergence analysis of a recent distributed algorithm, termed cloud K-SVD, that solves the problem of data-adaptive representations for big, distributed data. It is assumed that a number of geographically-distributed, interconnected sites have massive local data and they are collaboratively learning a sparsifying dictionary underlying these data using cloud K-SVD. This paper provides a rigorous analysis of cloud K-SVD that gives insights into its properties as well as deviations of the dictionaries learned at individual sites from a centralized solution in terms of different measures of local/global data and topology of the interconnections.

Exploiting multiple physical layers for communications has gained increasing interest recently to improve reliability and/or coverage range. Powerline and unlicensed wireless communication networks are attractive candidates to realize this objective because of their ubiquity. However, their performance can be severely degraded by impulsive noise (IN) and narrowband interference (NBI), respectively. In this paper, we exploit the inherent sparse structures of NBI and IN in the frequency and time domains, respectively, to propose an efficient joint estimation and mitigation scheme based on compressive sensing (CS) principles. Moreover, we investigate the metric of maximum expected coherence of our scheme for realistic powerline communication (PLC) and wireless channels, which provides some insight into its performance. Finally, our numerical experiments demonstrate the superiority of jointly processing the wireless and PLC channel outputs for CS-based NBI and IN mitigation over separate processing of individual channel outputs.

The linear model, in which a set of observations is assumed to be given by a linear combination of columns of a matrix (often termed a dictionary), has long been the mainstay of the statistics and signal processing literature. One particular challenge for inference under linear models is understanding the conditions on the dictionary under which reliable inference is possible. This challenge has attracted renewed attention in recent years, since many modern inference problems (e.g, high-dimensional statistics and compressed sensing) deal with the underdetermined setting, in which the number of observations is much smaller than the number of columns in the dictionary. This paper makes several contributions for this setting when the set of observations is given by a linear combination of a small number of groups of columns of the dictionary, termed the block-sparse case. First, it specifies conditions on the dictionary under which most block submatrices of the dictionary (often termed block subdictionaries) are well conditioned. This result is fundamentally different from prior work on block-sparse inference because: 1) it provides conditions that can be explicitly computed in polynomial time; 2) the given conditions translate into near-optimal scaling of the number of columns of the block subdictionaries as a function of the number of observations for a large class of dictionaries; and 3) it suggests that the spectral norm, rather than the column/block coherences of the dictionary, fundamentally limits the scaling of dimensions of the well-conditioned block subdictionaries. Second, in order to help understand the significance of this result in the context of block-sparse inference, this paper investigates the problems of block-sparse recovery and block-sparse regression in underdetermined settings. In both of these problems, this paper utilizes its result concerning conditioning of block subdictionaries and establishes that near-optimal block-sparse recovery and block-sparse regression is possible for a large class of dictionaries as long as the dictionary satisfies easily computable conditions and the coefficients describing the linear combination of groups of columns can be modeled through a mild statistical prior. Third, the paper reports extensive numerical experiments that highlight the effects of different measures of the dictionary in block-sparse inference problems.

This paper studies conditions for high-dimensional inference when the set of observations is given by a linear combination of a small number of groups of columns of a design matrix, termed the “block-sparse” case. In this regard, it first specifies conditions on the design matrix under which most of its block submatrices are well conditioned. It then leverages this result for average-case analysis of high-dimensional block-sparse recovery and regression. In contrast to earlier works, the results of this paper are fundamentally different because (i) they provide conditions on arbitrary designs that can be explicitly computed in polynomial time, (ii) the provided conditions translate into near-optimal scaling of the number of observations with the number of active blocks of the design matrix, and (iii) they suggest that the spectral norm, rather than the column/block coherences, of the design matrix fundamentally limits the performance of computational methods in high-dimensional settings.

This paper revisits the problem of data-adaptive learning of geometric signal structures based on the Union-of-Subspaces (UoS) model. In contrast to prior work, it motivates and investigates an extension of the classical UoS model, termed the Metric-Constrained Union-of-Subspaces (MC-UoS) model. In this regard, it puts forth two iterative methods for data-adaptive learning of an MC-UoS in the presence of complete and missing data. The proposed methods outperform existing approaches to learning a UoS in numerical experiments involving both synthetic and real data, which demonstrates effectiveness of both an MC-UoS model and the proposed methods.

There has been a considerable interest in quantifying the influence that one node exerts on another in a social network. Using directed information, we study the problem for a simple, two-node network that models two users in a Twitter network in which one user (Alice) influences the other user (Bob) through her tweets. Under this setup, we relate the problem of direction of influence to the calculation of directed information from the input to the output in a bufferless single-server timing queue. Based on this relationship, we compute the directed information rate from Alice to Bob and, under simplifying assumptions, relate that rate to the distributions of Alice's tweet timings and Bob's action timings.

We consider a colocated MIMO radar scenario, in which the receive antennas forward their measurements to a fusion center. Based on the received data, the fusion center formulates a matrix which is then used for target parameter estimation. When the receive antennas sample the target returns at Nyquist rate, and assuming that there are more receive antennas than targets, the data matrix at the fusion center is low-rank. When each receive antenna sends to the fusion center only a small number of samples, along with the sample index, the receive data matrix has missing elements, corresponding to the samples that were not forwarded. Under certain conditions, matrix completion techniques can be applied to recover the full receive data matrix, which can then be used in conjunction with array processing techniques, e.g., MUSIC, to obtain target information. Numerical results indicate that good target recovery can be achieved with occupancy of the receive data matrix as low as 50%.

Estimation of the level set of a function (i.e., regions where the function exceeds some value) is an important problem with applications in digital elevation mapping, medical imaging, astronomy, etc. In many applications, the function of interest is not observed directly. Rather, it is acquired through (linear) projection measurements, such as tomographic projections, interferometric measurements, coded-aperture measurements, and random projections associated with compressed sensing. This paper describes a new methodology for rapid and accurate estimation of the level set from such projection measurements. The key defining characteristic of the proposed method, called the projective level set estimator, is its ability to estimate the level set from projection measurements without an intermediate reconstruction step. This leads to significantly faster computation relative to heuristic “plug-in" methods that first estimate the function, typically with an iterative algorithm, and then threshold the result. The paper also includes a rigorous theoretical analysis of the proposed method, which utilizes results from the literature on concentration of measure and characterizes the estimator's performance in terms of geometry of the measurement operator and $\ell_1$-norm of the discretized function.

We introduce an approach to gossip algorithms that exploits three aspects of the wireless medium: superposition, broadcast, and power control. Instead of sending pairwise messages between neighbors on a fixed network topology, we construct gossip algorithms in which nodes can simultaneously recover multiple neighbors' messages and in which nodes can adjust the set of their neighbors by adjusting transmit power. We present two averaging algorithms, each based on a hierarchical clustering of the network. In the first algorithm, clusters of nodes transmit their estimates locally and randomly select a representative node for communications at the next level. In the second, each cluster mutually averages and then cooperatively transmits at the next level. For path-loss environments, these schemes achieve order-optimal or near order-optimal performance.

Identification of time-varying linear systems, which introduce both time-shifts (delays) and frequency-shifts (Doppler-shifts), is a central task in many engineering applications. This paper studies the problem of identification of underspread linear systems (ULSs), de fined as time-varying linear systems whose responses lie within a unit-area region in the delay-Doppler space, by probing them with a known input signal. The main contribution of the paper is that it characterizes conditions on the bandwidth and temporal support of the input signal that ensure identification of ULSs described by a finite set of delays and Doppler-shifts, and referred to as parametric ULSs, from single observations. In particular, the paper establishes that sufficiently-underspread parametric linear systems are identifiable as long as the time-bandwidth product of the input signal is proportional to the square of the total number of delay-Doppler pairs in the system. In addition, the paper describes a procedure that enables identification of parametric ULSs from an input train of pulses in polynomial time by exploiting recent results on sub-Nyquist sampling for time delay estimation and classical results on recovery of frequencies from a sum of complex exponentials.

Technological constraints severely limit the rate at which analog-to digital converters can reliably sample signals. Recently, Tropp et al. proposed an architecture, termed the random demodulator (RD), that attempts to overcome this obstacle for sparse bandlimited signals. One integral component of the RD architecture is a white noise like, bipolar modulating waveform that changes polarity at a rate equal to the signal bandwidth. Since there is a hardware limitation to how fast analog waveforms can change polarity without undergoing shape distortion, this leads to the RD also having a constraint on the maximum allowable bandwidth. In this paper, an extension of the RD, termed the constrained random demodulator (CRD), is pro posed that bypasses this bottleneck by replacing the original modulating waveform with a run-length limited (RLL) modulating wave form that changes polarity at a slower rate than the signal bandwidth. One of the main contributions of the paper is establishing that the CRD, despite employing a modulating waveform with correlations, enjoys some theoretical guarantees for certain RLL waveforms. In addition, for a given sampling rate and rate of change in the modulating waveform polarity, numerical simulations confirm that the CRD, using an appropriate RLL waveform, can sample a signal with an even wider bandwidth without a significant loss in performance.

The sparse signal processing literature often uses random sensing matrices to obtain performance guarantees. Unfortunately, in the real world, sensing matrices do not always come from random processes. It is therefore desirable to evaluate whether an arbitrary matrix, or frame, is suitable for sensing sparse signals. To this end, the present paper investigates two parameters that measure the coherence of a frame: worst-case and average coherence. We first provide several examples of frames that have small spectral norm, worst-case coherence, and average coherence. Next, we present a new lower bound on worst-case coherence and compare it to the Welch bound. Later, we propose an algorithm that decreases the average coherence of a frame without changing its spectral norm or worst-case coherence. Finally, we use worst-case and average coherence, as opposed to the Restricted Isometry Property, to garner near-optimal probabilistic guarantees on both sparse signal detection and reconstruction in the presence of noise. This contrasts with recent results that only guarantee noiseless signal recovery from arbitrary frames, and which further assume independence across the nonzero entries of the signal-in a sense, requiring small average coherence replaces the need for such an assumption.

The problem of model selection arises in a number of contexts, such as compressed sensing, subset selection in linear regression, estimation of structures in graphical models, and signal denoising. This paper generalizes the notion of incoherence in the existing literature on model selection and introduces two fundamental measures of coherence-termed as the worst-case coherence and the average coherence-among the columns of a design matrix. In particular, it utilizes these two measures of coherence to provide an in-depth analysis of a simple one-step thresholding (OST) algorithm for model selection. One of the key insights offered by the ensuing analysis is that OST is feasible for model selection as long as the design matrix obeys an easily verifiable property. In addition, the paper also characterizes the model-selection performance of OST in terms of the worst-case coherence, μ, and establishes that OST performs near-optimally in the low signal-to-noise ratio regime for N × C design matrices with μ ≈ O(N-1/2). Finally, in contrast to some of the existing literature on model selection, the analysis in the paper is nonasymptotic in nature, it does not require knowledge of the true model order, it is applicable to generic (random or deterministic) design matrices, and it neither requires submatrices of the design matrix to have full rank, nor does it assume a statistical prior on the values of the nonzero entries of the data vector.

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.

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

Sensing, processing and communication must be jointly optimized for efficient operation of resource-limited wireless sensor networks. We propose a novel source-channel matching approach for distributed field estimation that naturally integrates these basic operations and facilitates a unified analysis of the impact of key parameters (number of nodes, power, field complexity) on estimation accuracy. At the heart of our approach is a distributed source-channel communication architecture that matches the spatial scale of field coherence with the spatial scale of node synchronization for phase-coherent communication: the sensor field is uniformly partitioned into multiple cells and the nodes in each cell coherently communicate simple statistics of their measurements to the destination via a dedicated noisy multiple access channel (MAC). Essentially, the optimal field estimate in each cell is implicitly computed at the destination via the coherent spatial averaging inherent in the MAC, resulting in optimal power-distortion scaling with the number of nodes. In general, smoother fields demand lower per-node power but require node synchronization over larger scales for optimal estimation. In particular, optimal mean-square distortion scaling can be achieved with sub-linear power scaling. Our results also reveal a remarkable power-density tradeoff inherent in our approach: increasing the sensor density reduces the total power required to achieve a desired distortion. A direct consequence is that consistent field estimation is possible, in principle, even with vanishing total power in the limit of high sensor density.