In this paper, we study the adversarial robustness of deep neural networks (DNN) for classification against optimal classifiers. We look at the smallest magnitude of possible additive perturbations that can change a classifier's output. We provide a matrix-theoretic explanation of the adversarial fragility of DNNs for classification. In particular, our theoretical results show that the adversarial robustness of a neural network can degrade as the input dimension d increases. Analytically, we show that the adversarial robustness of neural networks can be only 1/√d of the best possible adversarial robustness of optimal classifiers. Our theories match remarkably well with empirical results. The matrix-theoretic explanation aligns with an earlier information-theoretic feature-compression-based explanation for the adversarial fragility of neural networks.

This paper considers the problem of recovering signals modeled by generative models from linear measurements contaminated with sparse outliers. We propose an outlier detection approach for reconstructing the ground-truth signals by solving an$\ell _{1}$norm minimization problem. We establish theoretical recovery guarantees for reconstruction of signals using generative models in the presence of outliers, giving lower bounds on the number of correctable outliers. Our results are applicable to both linear and nonlinear generator neural networks with an arbitrary number of layers. We propose an iterative and linearized alternating direction method of multipliers (ADMM) algorithm for solving the outlier detection problem via$\ell _{1}$norm minimization, and a gradient descent algorithm for solving the outlier detection problem via squared$\ell _{1}$norm minimization. We conduct extensive experiments using variational auto-encoder and deep convolutional generative adversarial networks, and the experimental results show that the signals can be successfully reconstructed under outliers using our approach. Our approach outperforms the traditional Lasso and$\ell _{2}$norm minimization approach.

This paper delves into the subject of designing a tree network, enabling the application of Distributed Dual Coordinate Ascent on a general tree network (DDCA-Tree) introduced in [1] – [3] for distributed Machine Learning (ML) process. We assume that a network is characterized by communication delays proportional to the distance between any two nodes. To efficiently managing distributed data across the network, we propose the Minimum Worst-Distance Tree (MWDT) algorithm for designing a tree network with a specified target depth yielding a network structure where the communication delay in worst path between a leaf node and its parent node is minimized, consequently enhancing the convergence speed of DDCA-Tree. In numerical experiments, to validate the effectiveness of our approach, we compared the communication delay in worst path on a tree network generated by our algorithm against a minimum spanning tree which provides minimum weight (i.e., distance) sum, and showed our network design has reduced distance in worst path.

The multi-agent reinforcement learning systems (MARL) based on the Markov decision process (MDP) have emerged in many critical applications. To improve the robust-ness/defense of MARL systems against adversarial attacks, the study of various adversarial attacks on reinforcement learning systems is very important. Previous works on adversarial attacks considered some possible features to attack in MDP, such as the action poisoning attacks, the reward poisoning attacks, and the state perception attacks. In this paper, we propose a brand-new form of attack called the camouflage attack in the MARL systems. In the camouflage attack, the attackers change the appearances of some objects without changing the actual objects themselves; and the camouflaged appearances may look the same to all the targeted recipient (victim) agents. The camouflaged appearances can mislead the recipient agents to misguided actions. We design algorithms that give the optimal camouflage attacks minimizing the rewards of recipient agents. Our numerical and theoretical results show that camouflage attacks can rival the more con-ventional, but likely more difficult state perception attacks. We also investigate cost-constrained camouflage attacks and showed numerically how cost budgets affect the attack performance.

We formulate the problem of performing optimal data compression under the constraints that compressed data can be used for accurate classification in machine learning. We show that this translates to a problem of minimizing the mutual information between data and its compressed version under the constraint on error probability of classification is small when using the compressed data for machine learning. We then provide analytical and computational methods to characterize the optimal trade-off between data compression and classification error probability. First, we provide an analytical characterization for the optimal compression strategy for data with binary labels. Second, for data with multiple labels, we formulate a set of convex optimization problems to characterize the optimal tradeoff, from which the optimal trade-off between the classification error and compression efficiency can be obtained by numerically solving the formulated optimization problems. We further show the improvement of our formulations over the information-bottleneck methods in classification performance.

Safety-critical traffic in Industrial Internet of Things (IIoT) requires real-time communications with high fault tolerance, bounded latency and low jitter.Time-Sensitive Software-Defined Network (TSSDN), which combines the deterministic transmission of Time-Sensitive Networking (TSN) with the centralized management of Software-Defined Networking (SDN), was recently proposed to support the real-time requirement in IIoT.The research on TSSDN has been receiving increasing interests, however, the existing work has limitations including 1) the functional safety of TSSDN cannot be guaranteed; and 2) the effect of the separation of data plane and control plane on the time-sensitivity of TSSDN has not been evaluated.Therefore, in this paper, we employ the timed model checker UPPAAL to formalize the TSSDN architecture.Firstly, we use the build-in checker in UPPAAL to verify deadlock-free property, functional safety property and starvation-free property of our model.Then, the total latency of frames forwarding and scheduling within a single switch is measured based on the model.We focus on the latency overhead of frames requesting processing rules from the controller, which is on average an additioanl 180µs latency in the worst case, but the impact of this delay on the time-sensitivity of TSSDN is tolerable.As far as we know, this is the first paper providing a formal verification and analysis approach for TSSDN architecture, which could benefit for both TSSDN designers as well as the researchers.

The rapid spread of SARS-CoV-2 has placed a significant burden on public health systems to provide swift and accurate diagnostic testing highlighting the critical need for innovative testing approaches for future pandemics. In this study, we present a novel sample pooling procedure based on compressed sensing theory to accurately identify virally infected patients at high prevalence rates utilizing an innovative viral RNA extraction process to minimize sample dilution. At prevalence rates ranging from 0-14.3%, the number of tests required to identify the infection status of all patients was reduced by 69.26% as compared to conventional testing in primary human SARS-CoV-2 nasopharyngeal swabs and a coronavirus model system. Our method provided quantification of individual sample viral load within a pool as well as a binary positive-negative result. Additionally, our modified pooling and RNA extraction process minimized sample dilution which remained constant as pool sizes increased. Compressed sensing can be adapted to a wide variety of diagnostic testing applications to increase throughput for routine laboratory testing as well as a means to increase testing capacity to combat future pandemics.

Due to the big size of data and limited data storage volume of a single computer or a single server, data are often stored in a distributed manner. Thus, performing large-scale machine learning operations with the distributed datasets through communication networks is often required. In this paper, we study the convergence rate of the distributed dual coordinate ascent for distributed machine learning problems in a general tree-structured network. Since a tree network model can be understood as the generalization of a star network, our algorithm can be thought of as the generalization of the distributed dual coordinate ascent in a star network. We provide the convergence rate of the distributed dual coordinate ascent over a general tree network in a recursive manner and analyze the network effect on the convergence rate. Secondly, by considering network communication delays, we optimize the distributed dual coordinate ascent algorithm to maximize its convergence speed. From our analytical result, we can choose the optimal number of local iterations depending on the communication delay severity to achieve the fastest convergence speed. In numerical experiments, we consider machine learning scenarios over communication networks, where local workers cannot directly reach to a central node due to constraints in communication, and demonstrate that the usability of our distributed dual coordinate ascent algorithm in tree networks.

By exploiting large antenna arrays, massive MIMO (multiple input multiple output) systems can greatly increase spectral and energy efficiency over traditional MIMO systems. However, increasing the number of antennas at the base station (BS) makes the uplink joint channel estimation and data detection (JED) challenging in massive MIMO systems. In this paper, we consider the JED problem for massive SIMO (single input multiple output) wireless systems, which is a special case of wireless systems with large antenna arrays. We propose exact Generalized Likelihood Ratio Test (GLRT) optimal JED algorithms with low expected complexity, for both constant-modulus and nonconstant-modulus constellations. We show that, despite the large number of unknown channel coefficients, the expected computational complexity of these algorithms is polynomial in channel coherence time (T) and the number of receive antennas (N), even when the number of receive antennas grows polynomially in the channel coherence time (N=O(T11) suffices to guarantee an expected computational complexity cubic in T and linear in N). Simulation results show that the GLRT-optimal JED algorithms achieve significant performance gains (up to 5 dB improvement in energy efficiency) with low computational complexity.

In[1], the following line was missing: “Weiyu Xu and Haider Ali Jasim Alshamary contributed equally to this article.”

Low-rank matrix recovery has found many applications in science and engineering such as machine learning, system identification, and Euclidean embedding. However, the lowrank matrix recovery problem is an NP hard problem and thus challenging. A commonly used heuristic approach is the nuclear norm minimization. Recently, some authors established the necessary and sufficient null space conditions for nuclear norm minimization to recover every possible low-rank matrix with rank at most r (the strong null space condition). Oymak et al. established a null space condition for successful recovery of a given low-rank matrix (the weak null space condition) using nuclear norm minimization, and derived the phase transition for the nuclear norm minimization. In this paper, we show that the weak null space condition proposed by Oymak et al. is only a sufficient condition for successful matrix recovery using nuclear norm minimization, and is not a necessary condition as claimed. We further give a weak null space condition for low-rank matrix recovery, which is both necessary and sufficient for the success of nuclear norm minimization. At the core of our derivation are an inequality for characterizing the nuclear norms of block matrices, and the conditions for equality to hold in that inequality.

Removing undesired reflections from images taken through the glass is of great importance in computer vision. It serves as a means to enhance the image quality for aesthetic purposes as well as to preprocess images in machine learning and pattern recognition applications. We propose a convex model to suppress the reflection from a single input image. Our model implies a partial differential equation with gradient thresholding, which is solved efficiently using Discrete Cosine Transform. Extensive experiments on synthetic and real-world images demonstrate that our approach achieves desirable reflection suppression results and dramatically reduces the execution time.

With explosion of data size and limited storage space at a single location, data are often distributed at different locations. We thus face the challenge of performing large-scale machine learning from these distributed data through communication networks. In this paper, we generalize the distributed dual coordinate ascent in a star network to a general tree structured network, and provide the convergence rate analysis of the general distributed dual coordinate ascent. In numerical experiments, we demonstrate that the performance of the distributed dual coordinate ascent in a tree network can outperform that of the distributed dual coordinate ascent in a star network when a network has a lot of communication delays between the center node and its direct child nodes.

We present a simple hypothesis about a compression property of artificial intelligence (AI) classifiers and present theoretical arguments to show that this hypothesis successfully accounts for the observed fragility of AI classifiers to small adversarial perturbations. We also propose a new method for detecting when small input perturbations cause classifier errors, and show theoretical guarantees for the performance of this detection method. We present experimental results with a voice recognition system to demonstrate this method. The ideas in this paper are motivated by a simple analogy between AI classifiers and the standard Shannon model of a communication system1.

In this paper, we solve the sum mean-squared error (MSE)-optimal 1-bit quantized precoding problem exactly for small-to-moderate sized multiuser multiple-input multiple-output (MU-MIMO) systems via branch and bound. To this end, we reformulate the original NP-hard precoding problem as a tree search and deploy a number of strategies that improve the pruning efficiency without sacrificing optimality. We evaluate the error-rate performance and the complexity of the resulting 1-bit branch-and-bound (BB-1) precoder, and compare its efficacy to that of existing, suboptimal algorithms for 1-bit precoding in MU-MIMO systems.

We consider the problem of recovering the superposition of R distinct complex exponential functions from compressed non-uniform time-domain samples. Total Variation (TV) minimization or atomic norm minimization was proposed in the literature to recover the R frequencies or the missing data. However, in order for TV minimization and atomic norm minimization to recover the missing data or the frequencies, the underlying R frequencies are required to be well-separated, even when the measurements are noiseless. This paper shows that the Hankel matrix recovery approach can super-resolve the R complex exponentials and their frequencies from compressed nonuniform measurements, regardless of how close their frequencies are to each other. We propose a new concept of orthonormal atomic norm minimization (OANM), and demonstrate that the success of Hankel matrix recovery in separation-free super-resolution comes from the fact that the nuclear norm of a Hankel matrix is an orthonormal atomic norm. More specifically, we show that, in traditional atomic norm minimization, the underlying parameter values must be well separated to achieve successful signal recovery, if the atoms are changing continuously with respect to the continuously-valued parameter. In contrast, for the OANM, it is possible the OANM is successful even though the original atoms can be arbitrarily close.

We consider the problem of spectral compressed sensing in continuous domain, which aims to recover a 2-dimensional spectrally sparse signal from partially observed time samples. The signal is assumed to be a superposition of s complex sinusoids. We propose a semidefinite program for the 2D signal recovery problem. Our model is able to handle large scale 2D signals of size 500 × 500, whereas traditional approaches only handle signals of size around 20 × 20.

Phaseless super-resolution refers to the problem of super-resolving a signal from only its low-frequency Fourier magnitude measurements. In this paper, we consider the phaseless super-resolution problem of recovering a sum of sparse Dirac delta functions which can be located anywhere in the continuous time-domain. For such signals in the continuous domain, we propose a novel Semidefinite Programming (SDP) based signal recovery method to achieve the phaseless super-resolution. This work extends the recent work of Jaganathan et al. [1], which considered phaseless super-resolution for discrete signals on the grid.

In this paper, the problem of identifying correlated components in a high-dimensional Gaussian vector is considered. In the setup considered, instead of having to take a full-vector observation at each time index, the observer is allowed to observe any subset or full set of components in the vector, and he has the freedom to design his sampling strategies over time. The observer aims to find an optimal sampling strategy and a decision rule to maximize the error exponent (per sample). We focus on sequential strategies, in which the sampling actions depend on the observations taken so far. We first derive performance bounds of any sequential sampling strategy. We then design a low complexity procedure called sequential diagonal procedure. We show that this low complexity sequential procedure substantially outperforms the optimal non-adaptive strategy when the strength of the signal is strong.

We propose fast algorithms that speed up or improve the performance of recovering spectrally sparse signals from un-derdetermined measurements. Our algorithms are based on a non-convex approach of using alternating projected gradient descent for structured matrix recovery. We apply this approach to two formulations of structured matrix recovery: Hankel and Toeplitz mosaic structured matrix, and Hankel structured matrix. Our methods provide better recovery performance, and faster signal recovery than existing algorithms, including atomic norm minimization.

We study the problem of recovering an n-dimensional BPSK signal from m linear noise-corrupted measurements using the box relaxation method which relaxes the discrete set {±1}n to the convex set [-1,1]n to obtain a convex optimization algorithm followed by hard thresholding. When the noise and measurement matrix have iid standard normal entries, we obtain an exact expression for the bit-wise probability of error Pe in the limit of n and m growing and m/n fixed. At high SNR our result shows that the Pe of box relaxation is within 3dB of the matched filter bound (MFB) for square systems, and that it approaches the (MFB) as m grows large compared to n. Our results also indicate that as m, n → ∞, for any fixed set of size k, the error events of the corresponding k bits in the box relaxation method are independent.

Characterizing the phase transitions of convex optimizations in recovering structured signals or data is of central importance in compressed sensing, machine learning and statistics. The phase transitions of many convex optimization signal recovery methods such as ℓ1minimization and nuclear norm minimization are well understood through recent years' research. However, rigorously characterizing the phase transition of total variation (TV) minimization in recovering sparse-gradient signal is still open. In this paper, we fully characterize the phase transition curve of the TV minimization. Our proof builds on Donoho, Johnstone and Montanari's conjectured phase transition curve for the TV approximate message passing algorithm (AMP), together with the linkage between the minmax Mean Square Error (MSE) of a denoising problem and the high-dimensional convex geometry for TV minimization.

In this paper, we propose an efficient optimal joint channel estimation and data detection algorithm for massive MIMO wireless systems. Our algorithm is optimal in terms of the generalized likelihood ratio test (GLRT). For massive MIMO systems, we show that the expected complexity of our algorithm grows polynomially in the channel coherence time. Simulation results demonstrate significant performance gains of our algorithm compared with suboptimal non-coherent detection algorithms. To the best of our knowledge, this is the first algorithm which efficiently achieves GLRT-optimal non-coherent detections for massive MIMO systems with general constellations.

By virtue of large antenna arrays, massive MIMO systems have a potential to yield higher spectral and energy efficiency in comparison with the conventional MIMO systems. This paper addresses uplink channel estimation in massive MIMO-OFDM systems with frequency selective channels. We propose an efficient distributed minimum mean square error (MMSE) algorithm that can achieve near optimal channel estimates at low complexity by exploiting the strong spatial correlation among antenna array elements. The proposed method involves solving a reduced dimensional MMSE problem at each antenna followed by a repetitive sharing of information through collaboration among neighboring array elements. To further enhance the channel estimates and/or reduce the number of reserved pilot tones, we propose a data-aided estimation technique that relies on finding a set of most reliable data carriers. Furthermore, we use stochastic geometry to quantify the pilot contamination, and in turn use this information to analyze the effect of pilot contamination on channel MSE. The simulation results validate our analysis and show near optimal performance of the proposed estimation algorithms.

We propose novel algorithms that enhance the performance of recovering unknown continuous-valued frequencies from undersampled signals. Our iterative reweighted frequency recovery algorithms employ the support knowledge gained from earlier steps of our algorithms as block prior information to enhance frequency recovery. Our methods improve the performance of the atomic norm minimization which is a useful heuristic in recovering continuous-valued frequency contents. Numerical results demonstrate that our block iterative reweighted methods provide both better recovery performance and faster speed than other known methods.

It is well known that ℓ1minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. Exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from independent identically distributed (i.i.d.) Gaussian measurements, have been computed and are referred to as weak thresholds. In this paper, we introduce a reweighted ℓ1recovery algorithm composed of two steps: 1) a standard ℓ1minimization step to identify a set of entries where the signal is likely to reside and 2) a weighted ℓ1minimization step where entries outside this set are penalized. For signals where the nonsparse component entries are independent and identically drawn from certain classes of distributions, (including most well-known continuous distributions), we prove a strict improvement in the weak recovery threshold. Our analysis suggests that the level of improvement in the weak threshold depends on the behavior of the distribution at the origin. Numerical simulations verify the distribution dependence of the threshold improvement very well, and suggest that in the case of i.i.d. Gaussian nonzero entries, the improvement can be quite impressive-over 20% in the example we consider.

Sparse recovery can recover sparse signals from a set of underdetermined linear measurements. Motivated by the need to monitor the key characteristics of large-scale networks from a limited number of measurements, this paper addresses the problem of recovering sparse signals in the presence of network topological constraints. Unlike conventional sparse recovery where a measurement can contain any subset of the unknown variables, we use a graph to characterize the topological constraints and allow an additive measurement over nodes (unknown variables) only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs, and the number of measurements by our construction is less than that needed by existing random constructions. Moreover, our construction for a line network is provably optimal in the sense that it requires the minimum number of measurements. A measurement construction algorithm for general graphs is also proposed and evaluated. For any given graph$G$with$n$nodes, we derive bounds of the minimum number of measurements needed to recover any$k$-sparse vector over$G$($M^{G}_{k,n}$). Using the Erdős-Rényi random graph as an example, we characterize the dependence of$M^{G}_{k,n}$on the graph structure. This paper suggests that$M^{G}_{k,n}$may serve as a graph connectivity metric.

Recent research in off-the-grid compressed sensing (CS) has demonstrated that, under certain conditions, one can successfully recover a spectrally sparse signal from a few time-domain samples even though the dictionary is continuous. In this paper, we extend off-the-grid CS to applications where some prior information about spectrally sparse signal is known. We specifically consider cases where a few contributing frequencies or poles, but not their amplitudes or phases, are known a priori. Our results show that equipping off-the-grid CS with the known-poles algorithm can increase the probability of recovering all the frequency components.

We design optimal 2 × N (2 <; N) matrices, with unit columns, so that the maximum condition number of all the submatrices comprising 3 columns is minimized. The problem has two applications. When estimating a 2-dimensional signal by using only three of N observations at a given time, this minimizes the worst-case achievable estimation error. It also captures the problem of optimum sensor placement for monitoring a source located in a plane, when only a minimum number of required sensors are active at any given time. For arbitrary N ≥ 3, we derive the optimal matrices which minimize the maximum condition number of all the submatrices of three columns. Surprisingly, a uniform distribution of the columns is not the optimal design for odd N ≥ 7.

Compressed sensing (CS) theory promises one can recover real-valued sparse signal from a small number of linear measurements. Motivated by network monitoring with link failures, we for the first time consider the problem of recovering signals that contain both real-valued entries and corruptions, where the real entries represent transmission delays on normal links and the corruptions represent failed links. Unlike conventional CS, here a measurement is real-valued only if it does not include a failed link, and it is corrupted otherwise. We prove that O((d + 1)max(d, k) log n) nonadaptive measurements are enough to recover all n-dimensional signals that contain k nonzero real entries and d corruptions. We provide explicit constructions of measurements and recovery algorithms. We also analyze the performance of signal recovery when the measurements contain errors.

In this paper, we consider robust system identification under sparse outliers and random noises. In our problem, system parameters are observed through a Toeplitz matrix. All observations are subject to random noises and a few are corrupted with outliers. We reduce this problem of system identification to a sparse error correcting problem using a Toeplitz structured real-numbered codingmatrix. We prove the performance guarantee of Toeplitz structured matrix in sparse error correction. Thresholds on the percentage of correctable errors for Toeplitz structured matrices are also established. When both outliers and observation noise are present, we have shown that the estimation error goes to 0 asymptotically as long as the probability density function for observation noise is not “vanishing” around 0.

The problem of sequentially finding an independent and identically distributed (i.i.d.) sequence that is drawn from a probability distribution F1by searching over multiple sequences, some of which are drawn from F1and the others of which are drawn from a different distribution F0, is considered. The sensor is allowed to take one observation at a time. It has been shown in a recent work that if each observation comes from one sequence, Cumulative Sum (CUSUM) test is optimal. In this paper, we propose a new approach in which each observation can be a linear combination of samples from multiple sequences. The test has two stages. In the first stage, namely scanning stage, one takes a linear combination of a pair of sequences with the hope of scanning through sequences that are unlikely to be generated from F1and quickly identifying a pair of sequences such that at least one of them is highly likely to be generated by F1. In the second stage, namely refinement stage, one examines the pair identified from the first stage more closely and picks one sequence to be the final sequence. The problem under this setup belongs to a class of multiple stopping time problems. In particular, it is an ordered two concatenated Markov stopping time problem. We obtain the optimal solution using the tools from the multiple stopping time theory. Numerical simulation results show that this search strategy can significantly reduce the searching time, especially when F1is rare.

This paper addresses the problem of sparse recovery with graph constraints in the sense that we can take additive measurements over nodes only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs. A general measurement construction algorithm is also proposed and evaluated. For any given graph G with n nodes, we derive order optimal upper bounds of the minimum number of measurements needed to recover any k-sparse vector over G (Mk,nG). Our study suggests that Mk,nGmay serve as a graph connectivity metric.

Determining the susceptibility distribution from the magnetic field measured in a magnetic resonance (MR) scanner is an ill-posed inverse problem, because of the presence of zeroes in the convolution kernel in the forward problem. An algorithm called morphology enabled dipole inversion (MEDI), which incorporates spatial prior information, has been proposed to generate a quantitative susceptibility map (QSM). The accuracy of QSM can be validated experimentally. However, there is not yet a rigorous mathematical demonstration of accuracy for a general regularized approach or for MEDI specifically. The error in the susceptibility map reconstructed by MEDI is expressed in terms of the acquisition noise and the error in the spatial prior information. A detailed analysis demonstrates that the error in the susceptibility map reconstructed by MEDI is bounded by a linear function of these two error sources. Numerical analysis confirms that the error of the susceptibility map reconstructed by MEDI is on the same order of the noise in the original MRI data, and comprehensive edge detection will lead to reduced model error in MEDI. Additional phantom validation and human brain imaging demonstrated the practicality of the MEDI method.

In this paper, motivated by network inference and tomography applications, we study the problem of compressive sensing for sparse signal vectors over graphs. In particular, we are interested in recovering sparse vectors representing the properties of the edges from a graph. Unlike existing compressive sensing results, the collective additive measurements we are allowed to take must follow connected paths over the underlying graph. For a sufficiently connected graph with n nodes, it is shown that, using O(k log(n)) path measurements, we are able to recover any k-sparse link vector (with no more than k nonzero elements), even though the measurements have to follow the graph path constraints. We mainly show that the computationally efficient ℓ1minimization can provide theoretical guarantees for inferring such k-sparse vectors with O(k log(n)) path measurements from the graph.

It is known that a high-dimensional sparse vector x* in TV can be recovered from low-dimensional measurements y = Ax* where Am×n(mp-minimization (0 ≤ p ≤ 1) as p varies, where ℓp-minimization returns a vector with the least ℓpquasi norm among all the vectors x satisfying Ax = y. Besides analyzing the performance of strong recovery where ℓp-minimization is re quired to recover all the sparse vectors up to certain sparsity, we also for the first time analyze the performance of "weak" recovery of ℓp-minimization (0 ≤ pm/n) → 1, we provide sharp thresholds of the sparsity ratio (i.e., percentage of nonzero entries of a vector) that differentiates the success and failure via ℓp-minimization. For strong recovery, the threshold strictly decreases from 0.5 to 0.239 as p increases from 0 to 1. Surprisingly, for weak recovery, the threshold is 2/3 for all p in [0, 1), while the threshold is 1 for ℓ1-minimization. We also explicitly demonstrate that ℓp-minimization (pp-minimization. For any a G (0.1), we provide bounds of the sparsity ratio for strong recovery and weak recovery, respectively, below which ℓp-minimization succeeds. Our bound of strong recovery improves on the existing bounds when a is large. In particular, regarding the recovery threshold, this paper argues that ℓp-minimization has a higher threshold with smaller p for strong recovery; the threshold is the same for all p for sectional recovery; and ℓp-minimization can outperform ℓp-minimization for weak recovery. These are in contrast to traditional wisdom that ℓp-minimization, though computationally more expensive, always has better sparse recovery ability than ℓ0-minimization since it is closer to ℓ1-minimization. Finally, we provide an intuitive explanation to our findings. Numerical examples are also used to un ambiguously confirm and illustrate the theoretical predictions.

ℓ1minimization is often used for recovering sparse signals from an under-determined linear system. In this paper, we focus on finding sharp performance bounds on recovering approximately sparse signals using ℓ1minimization under noisy measurements. While the restricted isometry property is powerful for the analysis of recovering approximately sparse signals with noisy measurements, the known bounds on the achievable sparsity1 level can be quite loose. The neighborly polytope analysis which yields sharp bounds for perfectly sparse signals cannot be readily generalized to approximately sparse signals. We start from analyzing a necessary and sufficient condition, the “balancedness” property of linear subspaces, for achieving a certain signal recovery accuracy. Then we give a unified null space Grassmann angle-based geometric framework to give sharp bounds on this “balancedness” property of linear subspaces. By investigating the “balancedness” property, this unified framework characterizes sharp quantitative tradeoffs between signal sparsity and the recovery accuracy of ℓ1minimization for approximately sparse signal. As a consequence, this generalizes the neighborly polytope result for perfectly sparse signals. Besides the robustness in the “strong” sense for all sparse signals, we also discuss the notions of “weak” and “sectional” robustness. Our results concern fundamental properties of linear subspaces and so may be of independent mathematical interest.

This paper studies the performance difference of joint routing and congestion control when either single-path routes or multipath routes are used. Our performance metric is the total utility achieved by jointly optimizing transmission rates using congestion control and paths using source routing. In general, this performance difference is strictly positive and hard to determine-in fact an NP-hard problem. To better estimate this performance gap, we develop analytical bounds to this “cost of not splitting” in routing. We prove that the number of paths needed for optimal multipath routing differs from that of optimal single-path routing by no more than the number of links in the network. We provide a general bound on the performance loss, which is independent of the number of source-destination pairs when the latter is larger than the number of links in a network. We also propose a vertex projection method and combine it with a greedy branch-and-bound algorithm to provide progressively tighter bounds on the performance loss. Numerical examples are used to show the effectiveness of our approximation technique and estimation algorithms.

It is now well understood that the ℓ1minimization algorithm is able to recover sparse signals from incomplete measurements and sharp recoverable sparsity thresholds have also been obtained for the ℓ1minimization algorithm. However, even though iterative reweighted ℓ1minimization algorithms or related algorithms have been empirically observed to boost the recoverable sparsity thresholds for certain types of signals, no rigorous theoretical results have been established to prove this fact. In this paper, we try to provide a theoretical foundation for analyzing the iterative reweighted ℓ1algorithms. In particular, we show that for a nontrivial class of signals, the iterative reweighted ℓ1minimization can indeed deliver recoverable sparsity thresholds larger than that given in. Our results are based on a high-dimensional geometrical analysis (Grassmann angle analysis) of the null-space characterization for ℓ1minimization and weighted ℓ1minimization algorithms.

It is well known that ℓ1minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. In fact, exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from iid Gaussian measurements, have been computed and are referred to as “weak thresholds”. In this paper, we introduce a reweighted ℓ1recovery algorithm composed of two steps: a standard ℓ1minimization step to identify a set of entries where the signal is likely to reside, and a weighted ℓ1minimization step where entries outside this set are penalized. For signals where the non-sparse component has iid Gaussian entries, we prove a “strict” improvement in the weak recovery threshold. Simulations suggest that the improvement can be quite impressive-over 20% in the example we consider.

An unknown vector f in Rncan be recovered from corrupted measurements y = Af + e where Am×n(m ≥ n) is the coding matrix if the unknown error vector e is sparse. We investigate the relationship of the fraction of errors and the recovering ability of lp-minimization (0p-norm" of y-Ax. We give sharp thresholds of the fraction of errors that is recoverable. If e is an arbitrary unknown vector, the threshold strictly decreases from 0.5 to 0.239 as p increases from 0 to 1. If e has fixed support and fixed signs on the support, the threshold is 2/3 for all p in (0, 1), and 1 for p = 1.

In this paper, we investigate the uniqueness of positive semidefinite matrix solution to compressed linear observations. We show that under a necessary and sufficient condition for the linear compressed observations operator, there will be a unique positive semidefinite matrix solution to the compressed linear observations. It is further shown, through concentration of measure phenomenon and sphere covering arguments, that a randomly generated Gaussian linear compressed observations operator will satisfy this necessary and sufficient condition with overwhelmingly large probability.

ℓ1minimization, also called Basis Pursuit, has been known to have strong sparse recovery performance both theoretically and empirically. Previously known analytical approaches for ℓ1minimization have limitations in deriving custom stability performance bounds for signals with sparsity (the number of nonzero elements) level beyond the ℓ1weak recovery threshold [6]. In this paper, instead of focusing on the static decoding results of ℓ1minimization, we develop a microscopic analytical approach by studying the dynamics of ℓ1minimization. This approach can give useful characterizations of ℓ1decoding results and lead to new performance bounds on ℓ1decoding error. Contrary to known stability results for ℓ1minimization below the ℓ1weak threshold, we prove that ℓ1minimization decoding errors can experience an explosive growth in terms of the signal tail immediately beyond the ℓ1minimization weak threshold. This new analytical approach is motivated by the applications of analyzing the emerging iterative reweighted ℓ1minimization algorithms.

In this paper we study a Markov Chain Monte Carlo (MCMC) Gibbs sampler for solving the integer least-squares problem. In digital communication the problem is equivalent to performing maximum likelihood (ML) detection in multiple-input multiple-output (MIMO) systems. While the use of MCMC methods for such problems has already been proposed, our method is novel in that we optimize the "temperature" parameter so that in steady state, i.e. after the Markov chain has mixed, there is only polynomially (rather than exponentially) small probability of encountering the optimal solution. More precisely, we obtain the largest value of the temperature parameter for this to occur, since the higher the temperature, the faster the mixing. This is in contrast to simulated annealing techniques where, rather than being held fixed, the temperature parameter is tended to zero. Simulations suggest that the resulting Gibbs sampler provides a computationally efficient way of achieving approximative ML detection in MIMO systems having a huge number of transmit and receive dimensions. In fact, they further suggest that the Markov chain is rapidly mixing. Thus, it has been observed that even in cases were ML detection using, e.g. sphere decoding becomes infeasible, the Gibbs sampler can still offer a near-optimal solution using much less computations.

In this paper we study the compressed sensing problem of recovering a sparse signal from a system of underdetermined linear equations when we have prior information about the probability of each entry of the unknown signal being nonzero. In particular, we focus on a model where the entries of the unknown vector fall into two sets, each with a different probability of being nonzero. We propose a weighted ¿1minimization recovery algorithm and analyze its performance using a Grassman angle approach. We compute explicitly the relationship between the system parameters (the weights, the number of measurements, the size of the two sets, the probabilities of being non-zero) so that an iid random Gaussian measurement matrix along with weighted ¿1minimization recovers almost all such sparse signals with overwhelming probability as the problem dimension increases. This allows us to compute the optimal weights. We also provide simulations to demonstrate the advantages of the method over conventional ¿1optimization.

It is well known in compressive sensing that l1minimization can recover the sparsest solution for a large class of underdetermined systems of linear equations, provided the signal is sufficiently sparse. In this paper, we compute sharp performance bounds for several different notions of robustness in sparse signal recovery via l1minimization. In particular, we determine necessary and sufficient conditions for the measurement matrix A under which l1minimization guarantees the robustness of sparse signal recovery in the “weak”, “sectional” and “strong” senses (e.g., robustness for “almost all” approximately sparse signals, or instead for “all” approximately sparse signals). Based on these characterizations, we are able to compute sharp performance bounds on the tradeoff between signal sparsity and signal recovery robustness in these various senses. Our results are based on a high-dimensional geometrical analysis of the null-space of the measurement matrix A. These results generalize the thresholds results for purely sparse signals [1], [3] and also present generalized insights on l1minimization for recovering purely sparse signals from a null-space perspective.

Expander graphs have been recently proposed to construct efficient compressed sensing algorithms. In particular, it has been shown that anyn-dimensional vector that isk-sparse can be fully recovered usingO(klogn) measurements and onlyO(klogn) simple recovery iterations. In this paper, we improve upon this result by considering expander graphs with expansion coefficient beyond3/4and show that, with the same number of measurements, onlyO(k) recovery iterations are required, which is a significant improvement whennis large. In fact, full recovery can be accomplished by at most2kvery simple iterations. The number of iterations can be reduced arbitrarily close tok, and the recovery algorithm can be implemented very efficiently using a simple priority queue with total recovery timeO(nlog(n/k))). We also show that by tolerating a small penalty on the number of measurements, and not on the number of recovery iterations, one can use the efficient construction of a family of expander graphs to come up with explicit measurement matrices for this method. We compare our result with other recently developed expander-graph-based methods and argue that it compares favorably both in terms of the number of required measurements and in terms of the time complexity and the simplicity of recovery. Finally, we will show how our analysis extends to give a robust algorithm that finds the position and sign of theksignificant elements of an almostk-sparse signal and then, using very simple optimization techniques, finds ak-sparse signal which is close to the bestk-term approximation of the original signal.

ML and near-ML MIMO detectors have attracted a lot of interest in recent years. However, almost all the reported implementations are delivered in ASICs or FPGAs. Our contribution is optimizing the near-ML MIMO detector for parallel programmable architectures, such as those with ILP and DLP features. In the proposed SSFE (selective spanning with fast enumeration), architecture-friendliness is explicitly introduced from the very beginning of the design flow. Importantly, high level algorithmic transformations make the dataflow pattern and structure fit architecture-characteristics very well. We enable abundant vector-parallelism with highly regular and deterministic dataflow in the SSFE; memory rearrangements, shuffling and non-predictable dynamism are all elaborately excluded. Hence, the SSFE can be easily parallelized and efficiently mapped onto ILP and DLP architectures. Furthermore, to fine-tune the SSFE on parallel architectures, extensive pre-compiler transformations are applied with the help of the application-level information. These optimize not only computation-operations but also address-generations and memory-accesses. Experiments show that the SSFE brings very efficient resource-utilizations on real-life VLIW architectures. Specifically, with the SSFE the percentage of NOPs instructions on VLIW is below 1%, even better than that achieved by the software-pipelined FFT. To the best of our knowledge, this is the first reported work about comprehensive optimizations of near-ML MIMO detectors for parallel programmable architectures.

It is well known that compressed sensing problems reduce to solving large under-determined systems of equations. To assure that the problem is well defined, i.e., that the solution is unique the vector of unknowns is of course assumed to be sparse. Nonetheless, even when the solution is unique, finding it in general may be computationally difficult. However, starting with the seminal work of [2], it has been shown that linear programming techniques, obtained from an l1-norm relaxation of the original non-convex problem, can provably find the unknown vector in certain instances. In particular, using a certain restricted isometry property, [2] shows that for measurement matrices chosen from a random Gaussian ensemble, l1optimization can find the correct solution with overwhelming probability even when the number of non-zero entries of the unknown vector is proportional to the number of measurements (and the total number of unknowns). The subsequent paper [1] uses results on neighborly polytopes from [5] to give a “sharp” bound on what this proportionality should be in the Gaussian case. In the current paper, we observe that what matters is not so much the distribution from which the entries of the measurement matrix A are drawn, but rather the statistics of the null-space of A. Using this observation, we provide an alternative proof of the main result of [2] by analyzing matrices whose null-space is isotropic (of which i.i.d. Gaussian ensembles are a special case).

The demand for high data rate reliable communications poses great challenges to the next generation wireless systems in highly dynamic mobile environments. In this paper, we investigate the joint maximum-likelihood (ML) channel estimation and signal detection problem for single-input multiple-output (SIMO) wireless systems with general modulation constellations and propose an efficient sequential decoder for finding the exact joint ML solution. Unlike other known methods, the new decoder can even efficiently find the joint ML solution under high spectral efficiency non-constant modulus modulation constellations. In particular, the new algorithm does not need such preprocessing steps as Cholesky or QR decomposition in the traditional sphere decoders for joint ML channel estimation and data detection. The elimination of such preprocessing not only reduces the number of floating point computations, but also will potentially lead to smaller size and power consumption in VLSI implementations while providing better numerical stability.

It is well known that compressed sensing problems reduce to solving large under-determined systems of equations. If we choose the compressed measurement matrix according to some appropriate distribution and the signal is sparse enough the l1optimization can exactly recover the ideally sparse signal with overwhelming probability [2], [1]. In the current paper, we will consider the case of the so-called approximately sparse signals. These signals are a generalized version of the ideally sparse signals. Letting the zero valued components of the ideally sparse signals to take the values of certain small magnitude one can construct the approximately sparse signals. Using a different but simple proof technique we show that the claims similar to those of [2] and [1] related to the proportionality of the number of large components of the signals to the number of measurements, hold for approximately sparse signals as well. Furthermore, using the same technique we compute the explicit values of what this proportionality can be if the compressed measurement matrix A has a rotationally invariant distribution of the null-space. We also give the quantitative tradeoff between the signal sparsity and the recovery robustness of the l1minimization. As it will turn out in an asymptotic case of the number of measurements the threshold result of [1] corresponds to a special case of our result.

Fast fading wireless environments pose a great challenge for achieving high spectral efficiency in next generation wireless systems. Joint maximum-likelihood (ML) channel estimation and signal detection is of great theoretical and practical interest, especially for multiple-input multiple-output(MIMO) systems where the multiple channel coefficients need to be estimated. However, this is a hard combinatorial optimization problem, for which obtaining efficient exact algorithms has been elusive for the general MIMO systems. In this paper, we propose an efficient branch-estimate-bound non-coherent optimization framework which provably achieves the exact ML joint channel estimation and data detection for general MIMO systems. Numerical results indicate that the exact joint ML method can achieve substantial performance improvements over suboptimal methods including iterative channel estimation and signal detection. We also derive analytical bounds on the computational complexity of the new exact joint ML method and show that its average complexity approaches a constant times the length of the coherence time, as the SNR approaches infinity.

Low-complexity tree search based exact maximum-likelihood (ML) detectors have gained attention for optimum signal detection in multiple-input multiple output (MIMO) wireless systems. In this paper, taking a fresher look at the closet lattice point search problem, we propose a new fast exact ML sphere decoder with ever-increasing radius (IR-SD). It is shown that IR-SD visits minimum number of tree nodes and is more computationally efficient than existing sphere decoders. IR-SD is also faster and requires less storage than ML stack detector. An upper-bound of expected computation and storage complexity of IR-SD independent of tree radius is derived. Numerical results validate that IR-SD greatly speeds up the ML detection than other sphere detectors while requiring less storage than ML stack algorithm. A factor-of-2.5 speed-up is observed over the depth-first Schnorr-Euchner sphere decoders when utilizing IR-SD in 16-QAM 10/spl times/10 complex MIMO system.

An M-ary orthogonal pulse polarity modulation (OP/sup 2/M) using modified orthogonal variable spreading factor codes (OVSF), i.e., a set of orthogonal Walsh codes, for time hopping ultra wideband (TH-UWB) communication systems is proposed. Under FCC power spectrum density (PSD) constraint for UWB, the proposed M-ary OP/sup 2/M system proves to be more power efficient than traditional bi-phase shift-keying (BPSK) modulation, binary and M-ary pulse position modulation (PPM) systems. OVSF codes are modified in OP/sup 2/M to smooth the signal PSD for meeting FCC PSD mask for UWB system. Reduced complexity receiver architecture provides tractable system complexity. Analytical and simulation results show that the proposed 32-ary OP/sup 2/M TH-UWB system is more power efficient than previous PPM and BPSK modulations.