Understanding the interactions between the central nervous system and muscular responses is essential for developing effective strategies to diagnose and manage movement disorders such as dystonia. This study addresses these complex interactions by introducing a novel non-linear forecasting method for time series data. We propose that mutual information, by detecting complex dependencies between time series, can uncover hidden relationships suggestive of Granger causality, thereby enhancing the scope and precision of causality analysis. Our approach emphasizes the selection of the most informative features for predicting the target variable through iterative extraction and evaluation. We employ an optimized gradient-boosted random forest algorithm, prioritizing features with the highest mutual information relative to the target variable. Additionally, a Granger causality metric, tailored for non-linear models, is developed to quantify the strength of the discovered interactions. Experimental validation on real physiological data demonstrates the effectiveness of our method in uncovering causal relationships and assessing feature importance, contributing to a deeper understanding of movement control mechanisms.

Cortico-muscular communication patterns reveal important information about motor control. However, inferring significant causal relationships between motor cortex electroencephalogram (EEG) and surface electromyogram (sEMG) of concurrently active muscles is challenging since relevant processes involved in muscle control are relatively weak compared to additive noise and background activities. In this paper, a framework for identification of cortico-muscular linear time invariant communication is proposed that simultaneously estimates model order and its parameters by enforcing sparsity and stationarity conditions in a convex optimization program. The experimental results demonstrate that our proposed algorithm outperforms existing techniques for autoregressive model estimation, in terms of computational speed and model identification for causality estimation.

Functional coupling between the cortex and muscle is commonly quantified by cortico-muscular coherence (CMC) between electroencephalogram (EEG) and electromyogram (EMG) signals. However, the presence of noise in EEG and EMG often degrades CMC, making it challenging to detect: some healthy subjects with good motor skills show no significant CMC. This study proposes an approach based on structured errors-in-variables (EIV) modelling to estimate components of the cortex and muscle signals involved in movement control from noisy EEG and EMG signals for the purpose of coherence estimation. We describe three algorithms to identify the underlying EIV system: one based on total least squares; the other two on structured total least squares, in which the Toeplitz data matrix structure is preserved. The effectiveness of the proposed method is assessed using simulated and neurophysiological data, where it achieved considerable improvements in coherence levels.

Short-and-sparse deconvolution (SaSD) aims to recover a short kernel and a long and sparse signal from their convolution. In the literature, formulation of blind deconvolution is either a convex programming via a matrix lifting of convolution, or a bilinear Lasso. Optimization solvers are typically based on bilinear factorizations. In this paper, we formulate SaSD as a non-convex optimization with a rank-one matrix constraint, hence referred to as Rank-One Constrained Optimization (ROCO). The solver is based on alternating direction method of multipliers (ADMM). It operates on the full rank-one matrix rather than bilinear factorizations. Closed form updates are derived for the efficiency of ADMM. Simulations include both synthetic data and real images. Results show substantial improvements in recovery accuracy (at least 19dB in PSNR for real images) and comparable runtime compared with benchmark algorithms based on bilinear factorization.

Typical methods for localisation in multipath environments focus on separating line-of-sight (LoS) from non-line-of-sight (NLoS) paths and only using LoS paths for localisation. A few works exploit NLoS paths but the methods are designed for some special settings. This paper presents a localisation method in which both LoS and NLoS paths are exploited for much more general settings. Its core is a convex optimisation formulation which handles multipath in a unified way, avoids error propagation between multiple stages, and guarantees a global convergence. In one of the case studies, single-antenna access points (APs) can locate a single-antenna mobile device (MD) even when all paths between them are NLoS, which according to the authors’ knowledge is the first time in the literature.

Though the blind super-resolution problem is nonconvex in nature, recent advance shows the feasibility of a convex formulation which gives the unique recovery guarantee. However, the convexification procedure is coupled with a huge computational cost and is therefore of great interests to investigate fast algorithms. To do so, we adapt an operator splitting approach ADMM and combine it with a novel preconditioning scheme. Numerical results show that the convergence rate is significantly improved by around two orders of magnitudes compared to the currently most adopted solver CVX. Also, by a Lasso type of formulation, the proposed solver is able to keep its high resolvability even under 0 dB SNR setting.

In this paper we consider a passive radar system which doesn't rely on the reception of reference signals from direct paths. A blind channel estimation based method is derived by exploring the relationship among the transmitted signal, the channel response and the received signal. With the help of this novel method, multiple incoming targets illuminated by a non-cooperative transmitter can be detected by a distributed radar system with at least two receivers. Numerical results demonstrate the feasibility and accuracy of the proposed method and some characteristics of the detector, namely, the performance as a function of the signal to noise ratio (SNR) and the number of radar receivers.

In this work, we develop a new framework for denoising in blind two-dimensional (2D) super-resolution that recovers a set of 2D continuous parameters as well as unknown waveforms from noisy samples. We apply the atomic norm to de-noise a weighted sum of time-delayed and frequency-shifted unknown waveforms. Moreover, we derive the theoretical mean-squared error of the estimator, and we show that it depends on the noise level and other system parameters. Then, we prove that when the number of samples satisfies certain bound, we can recover all the unknowns with high probability. Finally, we verify our theoretical findings using simulations.

Accurate wireless positioning of mobile agents is challenging in non-line-of-sight (NLOS) propagation environments due to unknown range or angle biases. In this paper, we develop a cooperative localization algorithm for mixed line-of-sight (LOS)/NLOS environments where the NLOS effect is mitigated by exploiting the geometric relationship of the range biases. In particular, we cast the localization problem as a detection-aided optimization program, in which all the distance measurements are initially treated as NLOS links with unknown nonnegative biases, followed by iterative agent position estimation and LOS identification. Moreover, the maximum-likelihood estimator for the agent positions and NLOS biases is relaxed into a semidefinite program where the geometric relationship of the biases is introduced as constraints. We also characterize the cooperation gain for LOS identification, and derive the constrained Cramér-Rao bound to show the localization accuracy improvement by the geometric constraints. Finally, numerical results validate the superior performance of the proposed algorithm compared with other competitive methods.

In this paper, we provide a new mathematical framework for identifying the parameters of a linear system from its response to multiple unknown waveforms. We assume that the system response is given by an unknown number of scaled versions of time-delayed and frequency-shifted unknown waveforms. Then, we develop a blind two-dimensional super-resolution framework that is based on the convex atomic norm frame-work to recover the continuous time-frequency shifts as well as the unknown waveforms. We prove that under a minimum separation condition between the time-frequency shifts and with a certain lower bound on the total number of the observed samples, all the unknowns in the system can be recovered precisely and with high probability. Simulation results that confirm the theoretical findings in the paper are provided.

Algorithms for dictionary learning aim to learn a dictionary under which training data have sparse representations. This paper addresses the dictionary update sub-problem, the goal of which is to update the dictionary and the corresponding sparse coefficients given a fixed sparsity pattern. It is a non-convex bilinear inverse problem, and hence challenging to solve. Inspired by a recent work by Ling and Strohmer, we re-formulate the dictionary update problem as a linear least squares problem, which is convex and easy to solve. Necessary bounds on the number of training samples required for a unique solution are derived when exact sparsity pattern is known. Further, for dictionary update with unknown sparsity patterns, an efficient iterative algorithm based on total least squares is developed. Embedding the new dictionary update procedure into an overall dictionary learning algorithm achieves better numerical performance compared to state of the art algorithms.

Identifiction of specific cortico-muscular interactions is essential for understanding sensorimotor control. These interactions are commonly studied by analyzing cortico-muscular coherence (CMC) between electroencephalogram (EEG) and surface electromyogram (sEMG) recorded synchronously under a motor control task. However, the presence of noise and components irrelevant to the monitored task weakens CMC so that it is often very difficult to detect. This study proposes an approach based on dictionary learning and sparse signal representation combined with a component selection algorithm to extract versions of EEG and sEMG signals which contain higher relative levels of coherent components. Evaluations using neurophysiological data show that the method achieves substantial increase in CMC levels.

It is now well understood that convex programming can be used to estimate the frequency components of a spectrally sparse signal from 2m+1 uniform temporal measurements. It is conjectured that a phase transition on the success of the total-variation regularization occurs when the distance between the spectral components of the signal to estimate crosses 1/m. We prove the necessity part of this conjecture by demonstrating that this regularization can fail whenever the spectral distance of the signal of interest is asymptotically equal to 1/m.

The line spectral estimation problem consists in recovering the frequencies of a complex valued time signal that is assumed to be sparse in the spectral domain from its discrete observations. As opposed to discretization-based methods for inverse problems, line spectral estimation reconstructs signals whose spectral supports lie continuously in the Fourier domain. If recent advances have shown that atomic norm relaxation produces highly robust estimates in this context, the computational cost of this approach remains, however, the major flaw for its application to practical systems. In this work, we aim to bridge the complexity issue by studying the atomic norm minimization problem from low dimensional projection of the signal samples. We derive conditions on the sub-sampling matrix under which the partial atomic norm can be expressed by a low-dimensional semidefinite program. Moreover, we illustrate the tightness of this relaxation by showing that it is possible to recover the original signal in poly-logarithmic time for two specific sub-sampling patterns.

The paper quantifies and compares the exact asymptotic performance of multiple measurement vector (MMV) and distributed sensing (DS) models. Both models assume multiple measurement instances yk= Akxk+ wk, k = 1, 2, ..., K. The difference is that MMV involves identical measurement matrices whereas DS allows different matrices for different measurement instances. It has been recognized that DS works better than MMV empirically. However, the quantification of the performance difference is not available in the literature. Our contribution is to quantify the asymptotic performance of MMV and DS in the asymptotic regime that the dimensions of the measurement matrices approach infinity proportionally but the number of measurement instances K remains a constant. The case study and numerical results justify the accuracy of the performance quantification. The analysis technique is based on the state evolution for approximate message passing.

This paper concerns sparse Bayesian learning (SBL) problem for group sparse signals. Group sparsity means that the signal components can be divided into groups, and the entries in one group are simultaneously zero or nonzero. In SBL, each group is controlled by a hyper-parameter. The marginal likelihood maximization (MLM) problem is to maximize the marginal likelihood of a given hyper-parameter by fixing all others. The main contribution of this paper is to solve the MLM problem by finding roots of a polynomial. Hence the global minimum of the marginal likelihood can be found efficiently. Furthermore, most large matrix inverses involved in MLM are replaced with the singular value decompositions of much smaller matrices, which substantially reduces the computational complexity. The proposed method is significantly different from the popular expectation maximization techniques in the literature where multiple iterations are required for MLM and the convergence to global optimum of marginal likelihood is not guaranteed.

The knowledge of CSI at the BS (CSIT) is required to achieve the high spectrum efficiency promised by massive MIMO. In Frequency-Division Duplex (FDD) Massive MIMO systems, the CSIT is obtained via downlink channel estimation and uplink channel feedback, However, the acquisition of CSIT is a very challenging problem in practical FDD massive MIMO systems with a large number of antennas. Recently, compressive sensing has been applied to reduce pilot and CSIT feedback overheads in massive MIMO systems by exploiting the underlying channel sparsity. However, standard sparse recovery algorithms have stringent requirement on the channel sparsity level for robust channel recovery and this severely limits the operating regime of the solution. To overcome this issue, we propose a joint burst LASSO algorithm to exploit additional joint burst-sparse structure in multi-user (MU) massive MIMO channels. Simulations show that the joint burst LASSO algorithm can alleviate the stringent requirement on the sparsity level for robust channel recovery and substantially enhance the channel estimation performance over existing solutions.

Super-resolution theory aims to estimate the discrete components lying in a continuous space that constitute a sparse signal with optimal precision. This work investigates the potential of recent super-resolution techniques for spectral estimation in multi-rate sampling systems. It shows that, under the existence of a common supporting grid, and under a minimal separation constraint, the frequencies of a spectrally sparse signal can be exactly jointly recovered from the output of a semidefinite program (SDP). The algorithmic complexity of this approach is discussed, and an equivalent SDP of minimal dimension is derived by extending the Gram parametrization properties of sparse trigonometric polynomials.

Power line communication (PLC) techniques present a no extra wire solution for the communication purpose in a smart grid due to the ubiquity and low cost. Moreover, the through-the-grid property of PLC has naturally extended its possible applications, including but not limited to the automatic meter reading, line quality monitoring, online diagnostics, and network tomography. To guarantee the performance of communications as well as other applications in PLC systems, accurate channel state information (CSI) acquisition should be performed regularly. However, the conventional pilot-based CSI acquisition approaches in PLC systems have not made full use of the channel characteristics and hence suffer from a low spectral efficiency. In this paper, by exploiting the parametric sparsity and discretizing the electrical length in the well-known PLC channel model, we formulate the non-sparse (either time domain or frequency domain) PLC channel into a compressive sensing (CS) applicable problem. Furthermore, we propose a spectrally efficient CSI acquisition scheme under the framework of Bayesian CS and extend it to the multiple-input multiple-output PLC by investigating the channel spatial correlation. Compared with the existing sparse CSI acquisition schemes for PLC, such as the annihilating filter-based and the estimating signal parameters via rotational invariance technique-based ones, the proposed scheme has better mean square error performance and noise robustness.

Massive MIMO is a promising technique for future 5G communications due to its high spectrum and energy efficiency. To realize its potential performance gain, accurate channel estimation is essential. However, due to massive number of antennas at the base station (BS), the pilot overhead required by conventional channel estimation schemes will be unaffordable, especially for frequency division duplex (FDD) massive MIMO. To overcome this problem, we propose a structured compressive sensing (SCS)-based spatio-temporal joint channel estimation scheme to reduce the required pilot overhead, whereby the spatio-temporal common sparsity of delay-domain MIMO channels is leveraged. Particularly, we first propose the nonorthogonal pilots at the BS under the framework of CS theory to reduce the required pilot overhead. Then, an adaptive structured subspace pursuit (ASSP) algorithm at the user is proposed to jointly estimate channels associated with multiple OFDM symbols from the limited number of pilots, whereby the spatio-temporal common sparsity of MIMO channels is exploited to improve the channel estimation accuracy. Moreover, by exploiting the temporal channel correlation, we propose a space-time adaptive pilot scheme to further reduce the pilot overhead. Additionally, we discuss the proposed channel estimation scheme in multicell scenario. Simulation results demonstrate that the proposed scheme can accurately estimate channels with the reduced pilot overhead, and it is capable of approaching the optimal oracle least squares estimator.

How to obtain accurate channel state information at the base station (CSIT) is a key implementation challenge behind frequency-division duplex massive MIMO systems. Recently, compressive sensing (CS) has been applied to reduce pilot and CSIT feedback overheads in massive MIMO systems by exploiting the underlying channel sparsity. However, brute-force applications of standard CS may not lead to good performance in massive MIMO systems, because standard sparse recovery algorithms have quite a stringent requirement on the sparsity level for robust recovery and this severely limits the operating regime of the solution. Moreover, since the channel support is usually correlated across time, it is possible to obtain partial channel support information (P-CSPI) from previously estimated channel support. Motivated by the above observations, we propose a P-CSPI aided burst Least Absolute Shrinkage and Selection Operator (LASSO) algorithm to exploit both the P-CSPI and additional structured properties of the sparsity, namely, the burst sparsity in massive MIMO channels. We also accurately characterize the asymptotic channel estimation error of the P-CSPI aided burst LASSO algorithm. Both the analysis and simulations show that the P-CSPI aided burst LASSO algorithm can alleviate the stringent requirement on the sparsity level for robust channel recovery and substantially enhance the channel estimation performance over existing solutions.

In this paper, by exploiting the special features of temporal correlations of dynamic sparse channels that path delays change slowly over time but path gains evolve faster, we propose the structured matching pursuit (SMP) algorithm to realize the reconstruction of dynamic sparse channels. Specifically, the SMP algorithm divides the path delays of dynamic sparse channels into two different parts to be considered separately, i.e., the common channel taps and the dynamic channel taps. Based on this separation, the proposed SMP algorithm simultaneously detects the common channel taps of dynamic sparse channels in all time slots at first, and then tracks the dynamic channel taps in each single time slot individually. Theoretical analysis of the proposed SMP algorithm provides a guarantee that the common channel taps can be successfully detected with a high probability, and the reconstruction distortion of dynamic sparse channels is linearly upper bounded by the noise power. Simulation results demonstrate that the proposed SMP algorithm has excellent reconstruction performance with competitive computational complexity compared with conventional reconstruction algorithms.

Power line communication (PLC) systems present a “no new wires” solution for the telecommunication access with the additional advantages of ubiquitous availability, easy installation and cost effectiveness. In this paper, by exploiting the parametric sparsity of the PLC channels, we propose a robust sparse channel state information (CSI) acquisition scheme under the framework of Bayesian compressive sensing (CS), which could significantly reduce the pilot overhead and improve the spectral efficiency. Compared to the current sparse CSI acquisition schemes for PLC, including those based on annihilating filter and estimating signal parameters via rotational invariance techniques (ESPRIT) algorithm, the proposed scheme is numerically demonstrated to have better mean squared error (MSE) performance. Furthermore, the proposed method is an appealing solution for practical PLC system, since the performance degradation due to the parameter discretization is not significant.

It has been widely recognized that structure information helps in sparse signal recovery. In this paper, a general form of block structure is considered, which is often referred to hierarchically sparse model. It is assumed that the unknown sparse signal can be divided into blocks, and a block contains either all zero components or a fraction of nonzero components. This model sits between the standard sparse model (without block structure) and the strict block sparse model (all entries in nonzero blocks are nonzero). The focus of this paper is to analyze the convex optimization approach to recover hierarchically sparse signals. The technique we employed is based on the approximated message passing framework and the associated state evolution. The minimum number of measurements required for exact recovery, also known as phase transition (PT), has been quantified in an asymptotic region. We show that the PT depends on two parameters: the fraction of nonzero components in nonzero blocks, and the uniformity of the magnitudes of nonzero components. Based on the PT analysis, we characterize the regions at which the convex optimization methods designed for the standard, hierarchically, and block sparse models are optimal respectively.

This work is motivated by a distributed compressed sensing (DCS) scenario where multiple sensors independently perform compressed sensing and the sparse signals share a common support. The heterogeneous case is considered where the numbers of measurements and the noise levels at different sensors may be different. To analyse the performance, we focus on a probability model for sparse signals and use the state evolution tool developed for the approximate message passing (AMP) technique. In the noise free case, we are able to quantify the asymptotic rate region for exact recovery. The rate region has a shape that is significantly different from that by information theoretic analysis and provides a guidance for resource allocation in practice. It shows that an equal allocation of the number of measurements across sensors is strictly suboptimal. Finally, we also study the effect of the correlation among nonzero components from different sparse signals, which appears in many practical scenarios.

This paper provides a proof of global convergence of gradient search for low-rank matrix approximation. Such approximations have recently been of interest for large-scale problems, as well as for dictionary learning for sparse signal representations and matrix completion. The proof is based on the interpretation of the problem as an optimization on the Grassmann manifold and Fubiny-Study distance on this space.

We consider the dictionary learning problem for the analysis model based sparse representation. A novel algorithm is proposed by adapting the synthesis model based simultaneous codeword optimisation (SimCO) algorithm to the analysis model. This algorithm assumes that the analysis dictionary contains unit Ł2-norm atoms and trains the dictionary by the optimisation on manifolds. This framework allows one to update multiple dictionary atoms in each iteration, leading to a computationally efficient optimisation process. We demonstrate the competitive performance of the proposed algorithm using experiments on both synthetic and real data, as compared with three baseline algorithms, Analysis K-SVD, analysis operator learning (AOL) and learning overcomplete sparsifying transforms (LOST), respectively.

The Sparse Bayesian learning (SBL) framework has been successfully adopted for sparse signal recovery. In SBL inference can be performed either via Type-II Maximum Likelihood or by following a Variational approach. When employing uninformative prior distributions, fast algorithms have been proposed for both renditions of SBL and it has been proven that they are equivalent. Unfortunately the use of such priors prohibits the incorporation of prior statistical information which can be beneficial in terms of convergence and accuracy. A modified variational approach is proposed, resulting in a fast variational algorithm for informative priors. A fixed point analysis is performed with the major challenge being the highly involved analytical expressions for the points in the fixed set. The given theoretical analysis demonstrates how this issue can be circumvented. Comprehensive empirical results are given to support the claims.

This paper studies the problem of power allocation in compressed sensing when different components in the unknown sparse signal have different probability to be non-zero. Given the prior information of the non-uniform sparsity and the total power budget, we are interested in how to optimally allocate the power across the columns of a Gaussian random measurement matrix so that the mean squared reconstruction error is minimized. Based on the state evolution technique originated from the work by Donoho, Maleki, and Montanari, we revise the so called approximate message passing (AMP) algorithm for the reconstruction and quantify the MSE performance in the asymptotic regime. Then the closed form of the optimal power allocation is obtained. The results show that in the presence of measurement noise, uniform power allocation, which results in the commonly used Gaussian random matrix with i.i.d. entries, is not optimal for non-uniformly sparse signals. Empirical results are presented to demonstrate the performance gain.

In this work we are interested in the problem of reconstructing time-varying signals for which the support is assumed to be sparse. For a single time instance it is possible to reconstruct the original signal efficiently by employing a suitable algorithm for sparse signal recovery, given the sparsity level of the signal. In the case of time-varying sparse signals the sparsity level is not necessarily known a-priori. Furthermore conventional tracking by Kalman filtering fails to promote sparsity. Instead, a hierarchical Bayesian model is used in the tracking process which succeeds in modelling sparsity. One theorem is provided that extends previous work by providing some more general results. A second theorem gives the conditions under which all sparse signals are recovered exactly. It is demonstrated that the proposed method succeeds in recovering time-varying sparse signals with greater accuracy than the classic Kalman filter approach.

Typical algorithms for dictionary learning iteratively perform two steps: sparse approximation and dictionary update. This paper focuses on the latter. While various algorithms have been proposed for dictionary update, the global optimality is generally not guaranteed. Interestingly, the main reason for an optimization procedure not converging to a global optimum is not local minima or saddle points but singular points where the objective function is not continuous. To address the singularity issue, we propose the so called smoothed SimCO, where the original objective function is replaced with a continuous counterpart. It can be proved that in the limit case, the new objective function is the best possible lower semi-continuous approximation of the original one. A Newton CG method is implemented to solve the corresponding optimization problem. Simulations demonstrate the proposed method significantly improves the performance.

Dictionary learning aims to adapt elementary codewords directly from training data so that each training signal can be best approximated by a linear combination of only a few codewords. Following the two-stage iterative processes: sparse coding and dictionary update, that are commonly used, for example, in the algorithms of MOD and K-SVD, we propose a novel framework that allows one to update an arbitrary set of codewords and the corresponding sparse coefficients simultaneously, hence termed simultaneous codeword optimization (SimCO). Under this framework, we have developed two algorithms, namely the primitive and the regularized SimCO. Simulations are provided to show the advantages of our approach over the K-SVD algorithm in terms of both learning performance and running speed.

The low-rank matrix completion problem can be succinctly stated as follows: given a subset of the entries of a matrix, find a low-rank matrix consistent with the observations. While several low-complexity algorithms for matrix completion have been proposed so far, it remains an open problem to devise -type search procedures with provable performance guarantees. The standard approach to the problem, which involves the minimization of an objective function defined using the Frobenius metric, has inherent difficulties: the objective function is not continuous and the solution set is not closed. To address this problem, we consider an optimization procedure that searches for a column (or row) space that is geometrically consistent with the partial observations. The geometric objective function is continuous everywhere and the solution set is the closure of the solution set of the Frobenius metric. We also preclude the existence of local minimizers, and hence establish strong performance guarantees, for special completion scenarios, which do not require matrix incoherence and hold with probability one for arbitrary matrix size.

The low-rank matrix completion problem can be stated as follows: given a subset of the entries of a matrix, find a low-rank matrix consistent with the observations. There exist several low-complexity algorithms for low-rank matrix completion which focus on the minimization of the Frobenius norm of the matrix projection residue. This optimization framework has inherent difficulties: the objective function is not continuous and the solution set is not closed. To address this problem, we propose a geometric objective function to replace the Frobenius norm: the new objective function is continuous everywhere and the solution set is the closure of the solution set of the Frobenius metric. Furthermore, using the geometric objective function and a simple gradient descent procedure, we are able to preclude the existence of local minimizers, and hence establish strong performance guarantees for special completion scenarios, which do not require matrix incoherence or large matrix size.

We study the average distortion introduced by scalar, vector, and entropy coded quantization of compressive sensing (CS) measurements. The asymptotic behavior of the underlying quantization schemes is either quantified exactly or characterized via bounds. We adapt two benchmark CS reconstruction algorithms to accommodate quantization errors, and empirically demonstrate that these methods significantly reduce the reconstruction distortion when compared to standard CS techniques.

A new algorithm, termed subspace evolution and transfer (SET), is proposed for solving the consistent matrix completion problem. In this setting, one is given a subset of the entries of a low-rank matrix, and asked to find one low-rank matrix consistent with the given observations. We show that this problem can be solved by searching for a column space that matches the observations. The corresponding algorithm consists of two parts - subspace evolution and subspace transfer. In the evolution part, we use a line search procedure to refine the column space. However, line search is not guaranteed to converge, as there may exist barriers along the search path that prevent the algorithm from reaching a global optimum. To address this problem, in the transfer part, we design mechanisms to detect barriers and transfer the estimated column space from one side of the barrier to the another. The SET algorithm exhibits excellent empirical performance for very low-rank matrices.

One of the main computational challenges in digital fingerprinting systems is the complexity of colluder identification. Inspired by compressive sensing approaches for support recovery of sparse vectors, we propose a novel list-decoding approach for partial colluder identification. We also derive formulas for the minimum codelength required for identifying a nonzero fraction of colluders based on noiseless and noisy measurements, using simple single-step correlation maximization techniques.

We study the average distortion introduced by scalar, vector, and entropy coded quantization of compressive sensing (CS) measurements. The asymptotic behavior of the underlying quantization schemes is either quantified exactly or characterized via bounds. We also modify two benchmark CS reconstruction algorithms to accommodate quantization effects, and empirically demonstrate that these methods significantly reduce the reconstruction distortion.

We propose a new compressive sensing scheme, based on codes of graphs, that allows for joint design of sensing matrices and low complexity reconstruction algorithms. The compressive sensing matrices can be shown to offer asymptotically optimal performance when used in combination with OMP methods. For more elaborate greedy reconstruction schemes, we propose a new family of list decoding and multiple-basis belief propagation algorithms. Our simulation results indicate that the proposed CS scheme offers good complexity-performance tradeoffs for several classes of sparse signals.

We study the average distortion introduced by quantizing compressive sensing measurements. Both uniform quantization and non-uniform quantization are considered. The asymptotic distortion-rate functions are obtained when the measurement matrix belongs to certain random matrix ensembles. Furthermore, we adapt two well-known compressive sensing reconstruction algorithms to accommodate the quantization effects. The performance of the new reconstruction methods is assessed through extensive computer simulations.

We analyze the effect of finite rate feedback on code-division multiple-access (CDMA) signature optimization and multiple-input multiple-output (MIMO) beamforming vector selection. In CDMA signature optimization, for a particular user, the receiver selects a signature vector from a codebook to best avoid interference from other users, and then feeds the corresponding index back to the specified user. For MIMO beamforming vector selection, the receiver chooses a beamforming vector from a given codebook to maximize the instantaneous information rate, and feeds back the corresponding index to the transmitter. These two problems are dual: both can be modeled as selecting a unit norm vector from a finite size codebook to ldquomatchrdquo a randomly generated Gaussian matrix. Assuming that the feedback link is rate limited, our main result is an exact asymptotic performance formula where the length of the signature/beamforming vector, the dimensions of interference/channel matrix, and the feedback rate approach infinity with constant ratios. The proof rests on the large deviations of the underlying random matrix ensemble. Further, we show that random codebooks generated from the isotropic distribution are asymptotically optimal not only on average, but also in probability.

It is well known that multiple-input multiple-output (MIMO) systems have high spectral efficiency, especially when channel state information at the transmitter (CSIT) is available. In many practical systems, it is reasonable to assume that the CSIT is obtained by a limited (i.e., finite rate) feedback and is therefore imperfect. We consider the design problem of how to use the limited feedback resource to maximize the achievable information rate. In particular, we develop a low complexity power on/off strategy with beamforming (or Grassmann precoding), and analytically characterize its performance. Given the eigenvalue decomposition of the covariance matrix of the transmitted signal, refer to the eigenvectors as beams, and to the corresponding eigenvalues as the beam's power. A power on/off strategy means that a beam is either turned on with a constant power, or turned off. We will first assume that the beams match the channel perfectly and show that the ratio between the optimal number of beams turned on and the number of antennas converges to a constant when the numbers of transmit and receive antennas approach infinity proportionally. This motivates our power on/off strategy where the number of beams turned on is independent of channel realizations but is a function of the signal-to-noise ratio (SNR). When the feedback rate is finite, beamforming cannot be perfect, and we characterize the effect of imperfect beamforming by quantization bounds on the Grassmann manifold. By combining the results for power on/off and beamforming, a good approximation to the achievable information rate is derived. Simulations show that the proposed strategy is near optimal and the performance approximation is accurate for all experimented SNRs.

We introduce a new family of codes, termed weighted superimposed codes (WSCs). This family generalizes the class of Euclidean superimposed codes (ESCs), used in multiuser identification systems. WSCs allow for discriminating all bounded, integer-valued linear combinations of real-valued codewords that satisfy prescribed norm and nonnegativity constraints. By design, WSCs are inherently noise tolerant. Therefore, these codes can be seen as special instances of robust compressed sensing schemes. The main results of the paper are lower and upper bounds on the largest achievable code rates of several classes of WSCs. These bounds suggest that, with the codeword and weighting vector constraints at hand, one can improve the code rates achievable by standard compressive sensing techniques.

We propose a new method for reconstruction of sparse signals with and without noisy perturbations, termed the subspace pursuit algorithm. The algorithm has two important characteristics: low computational complexity, comparable to that of orthogonal matching pursuit techniques when applied to very sparse signals, and reconstruction accuracy of the same order as that of linear programming (LP) optimization methods. The presented analysis shows that in the noiseless setting, the proposed algorithm can exactly reconstruct arbitrary sparse signals provided that the sensing matrix satisfies the restricted isometry property with a constant parameter. In the noisy setting and in the case that the signal is not exactly sparse, it can be shown that the mean-squared error of the reconstruction is upper-bounded by constant multiples of the measurement and signal perturbation energies.

We consider multiaccess multiple-input multiple-output (MIMO) systems with finite rate feedback with the aim of understanding how to efficiently employ the given feedback resource to maximize the sum rate. A joint quantization and feedback strategy is proposed: the base station selects the strongest users, jointly quantizes their strongest eigen-channel vectors and broadcasts a common feedback to all the users. This joint strategy differs from an individual strategy in which quantization and feedback are performed independently across users, and it improves upon the individual strategy in the same way that vector quantization improves upon scalar quantization. To analyze the proposed strategy, the effect of user selection is described by extreme order statistics, while the effect of joint quantization is quantified through what we term "the composite Grassmann manifold". The achievable sum rate is then estimated using random matrix theory providing an analytic benchmark for the performance.

Compressive sensing microarrays (CSM) are DNA-based sensors that operate using the principle of compressive sensing (CS). In contrast to conventional DNA microarrays, in which each genetic sensor is designed to respond to a single target, in a CSM each sensor responds to a group of targets. We study the problem of designing CS probes that simultaneously account for both the constraints from group testing theory and the biochemistry of probe-target DNA hybridization. Our results show that, in order to achieve accurate hybridization profiling, consensus probe sequences are required to have sequence homology of at least 80% with all targets to be detected. Furthermore, experiments show that out-of-equilibrium datasets are usually as accurate as those obtained from equilibrium conditions. Consequently, one can use CSMs in applications for which only short hybridization times are allowed.

We introduce a new family of codes, termed weighted Euclidean superimposed codes (WESCs). This family generalizes the class of Euclidean superimposed codes, used in multiuser identification systems. WESCs allow for discriminating bounded, integer-valued linear combinations of real-valued codewords, and can therefore also be seen as a specialization of compressed sensing schemes. We present lower and upper bounds on the largest size of a member of the WESCs family, and show how to use classical coding-theoretic and new compressed sensing analytical tools to devise low-complexity decoding algorithms for these codes.

This paper considers broadcast channels with L antennas at the base station and m single-antenna users, where L and m are typically of the same order. We assume that only partial channel state information is available at the base station through a finite rate feedback. Our key observation is that the optimal number of on-users (users turned on), say s, is a function of signal-to-noise ratio (SNR) and feedback rate. In support of this, an asymptotic analysis is employed where L, m and the feedback rate approach infinity linearly. We derive the asymptotic optimal feedback strategy as well as a realistic criterion to decide which users should be turned on. The corresponding asymptotic throughput per antenna, which we define as the spatial efficiency, turns out to be a function of the number of on-users s, and therefore s must be chosen appropriately. Based on the asymptotics, a scheme is developed for systems with finite many antennas and users. Compared with other studies in which s is presumed constant, our scheme achieves a significant gain. Furthermore, our analysis and scheme are valid for heterogeneous systems where different users may have different path loss coefficients and feedback rates.

The Grassmann manifold Gn,p(L) is the set of all p-dimensional planes (through the origin) in the n-dimensional Euclidean space Ln, where L is either R or C. This paper considers the quantization problem in which a source in Gn,p(L) is quantized through a code in Gn,q(L), with p and q not necessarily the same. The analysis is based on the volume of a metric ball in Gn,p(L) with center in Gn,q(L), and our chief result is a closed-form expression for the volume of a metric ball of radius at most one. This volume formula holds for arbitrary n, p, q, and L, while previous results pertained only to some special cases. Based on this volume formula, several bounds are derived for the rate-distortion tradeoff assuming that the quantization rate is sufficiently high. The lower and upper bounds on the distortion rate function are asymptotically identical, and therefore precisely quantify the asymptotic rate-distortion tradeoff. We also show that random codes are asymptotically optimal in the sense that they achieve the minimum possible distortion in probability as n and the code rate approach infinity linearly. Finally, as an application of the derived results to communication theory, we quantify the effect of beamforming matrix selection in multiple-antenna communication systems with finite rate channel state feedback.

The Grassmann manifold Gn,p (L) is the set of all p-dimensional planes (through the origin) in the n-dimensional Euclidean space Ln, where L is either R or C. This paper considers an unequal dimensional quantization in which a source in Gn,q (L) is quantized through a code in Gn,p (L), where p and q are not necessarily the same. The analysis for unequal dimensional quantization is based on the volume of a metric ball in Gn,q (L) whose center is in Gn,p (L). Our chief result is to show that as n, p, q and the square radius approach infinity with constant ratios, the volume of a metric ball "grows" as exp (-n2V (1 + o (1))) for a computable constant V ges 0. This result is stronger than our previous volume formula which is only valid when the radius is at most one. The tools behind the present result include large deviation techniques and equilibrium measure ideas from potential theory. Based on the volume growth formula, the rate distortion tradeoff is precisely quantified in our asymptotic region. Finally, we prove that random codes are asymptotically optimal in probability.

The Grassmann manifold Gn,p(L) is the set of all p-dimensional planes (through the origin) in the n-dimensional Euclidean space Ln, where L is either R or C. This paper considers an unequal dimensional quantization in which a source in Gn,p(L) is quantized through a code in Gn,q(L), where p and q are not necessarily the same. It is different from most works in literature where p ≡ q. The analysis for unequal dimensional quantization is based on the volume of a metric ball in Gn,p(L) whose center is in Gn,q. Our chief result is a closed-form formula for the volume of a metric ball when the radius is sufficiently small. This volume formula holds for Grassmann manifolds with arbitrary n, p, q and L, while previous results pertained only to some special cases. Based on this volume formula, several bounds are derived for the rate distortion tradeoff assuming the quantization rate is sufficiently high. The lower and upper bounds on the distortion rate function are asymptotically identical, and so precisely quantify the asymptotic rate distortion tradeoff. We also show that random codes are asymptotically optimal in the sense that they achieve the minimum achievable distortion with probability one as n and the code rate approach infinity linearly. Finally, we discuss some applications of the derived results to communication theory. A geometric interpretation in the Grassmann manifold is developed for capacity calculation of additive white Gaussian noise channel.

This paper considers the quantization problem on the Grassmann manifold with dimension n and p. The unique contribution is the derivation of a closed-form formula for the volume of a metric ball in the Grassmann manifold when the radius is sufficiently small. This volume formula holds for Grassmann manifolds with arbitrary dimension n and p, while previous results are only valid for either p = 1 or a fixed p with asymptotically large n. Based on the volume formula, the Gilbert-Varshamov and Hamming bounds for sphere packings are obtained. Assuming a uniformly distributed source and a distortion metric based on the squared chordal distance, tight lower and upper bounds are established for the distortion rate tradeoff. Simulation results match the derived results. As an application of the derived quantization bounds, the information rate of a multiple-input multiple-output (MIMO) system with finite-rate channel-state feedback is accurately quantified for arbitrary finite number of antennas, while previous results are only valid for either multiple-input single-output (MISO) systems or those with asymptotically large number of transmit antennas but fixed number of receive antennas.

This paper quantifies the information rate of multiple-input multiple-output (MIMO) systems with finite rate channel state feedback and power on/off strategy. In power on/off strategy, a beamforming vector (beam) is either turned on (denoted by on-beam) with a constant power or turned off. We prove that the ratio of the optimal number of on-beams and the number of antennas converges to a constant for a given signal-to-noise ratio (SNR) when the number of transmit and receive antennas approaches infinity simultaneously and when beamforming is perfect. Based on this result, a near optimal strategy, i.e., power on/off strategy with a constant number of on-beams, is discussed. For such a strategy, we propose the power efficiency factor to quantify the effect of imperfect beamforming. A formula is proposed to compute the maximum power efficiency factor achievable given a feedback rate. The information rate of the overall MIMO system can be approximated by combining the asymptotic results and the formula for power efficiency factor. Simulations show that this approximation is accurate for all SNR regimes