• Coarrays, MUSIC, and the Cram\'er Rao Bound(1605.03620)

Dec. 13, 2016 stat.AP
Sparse linear arrays, such as co-prime arrays and nested arrays, have the attractive capability of providing enhanced degrees of freedom. By exploiting the coarray structure, an augmented sample covariance matrix can be constructed and MUSIC (MUtiple SIgnal Classification) can be applied to identify more sources than the number of sensors. While such a MUSIC algorithm works quite well, its performance has not been theoretically analyzed. In this paper, we derive a simplified asymptotic mean square error (MSE) expression for the MUSIC algorithm applied to the coarray model, which is applicable even if the source number exceeds the sensor number. We show that the directly augmented sample covariance matrix and the spatial smoothed sample covariance matrix yield the same asymptotic MSE for MUSIC. We also show that when there are more sources than the number of sensors, the MSE converges to a positive value instead of zero when the signal-to-noise ratio (SNR) goes to infinity. This finding explains the "saturation" behavior of the coarray-based MUSIC algorithms in the high SNR region observed in previous studies. Finally, we derive the Cram\'er-Rao bound (CRB) for sparse linear arrays, and conduct a numerical study of the statistical efficiency of the coarray-based estimator. Experimental results verify theoretical derivations and reveal the complex efficiency pattern of coarray-based MUSIC algorithms.
• The $\beta$-model for Random Graphs --- Regression, Cram\'er-Rao Bounds, and Hypothesis Testing(1611.05699)

Nov. 14, 2016 stat.ME
We develop a maximum-likelihood based method for regression in a setting where the dependent variable is a random graph and covariates are available on a graph-level. The model generalizes the well-known $\beta$-model for random graphs by replacing the constant model parameters with regression functions. Cram\'er-Rao bounds are derived for the undirected $\beta$-model, the directed $\beta$-model, and the generalized $\beta$-model. The corresponding maximum likelihood estimators are compared to the bounds by means of simulations. Moreover, examples are given on how to use the presented maximum likelihood estimators to test for directionality and significance. Last, the applicability of the model is demonstrated using dynamic social network data describing communication among healthcare workers.
• Inertial Sensor Arrays, Maximum Likelihood, and Cram\'er-Rao Bound(1509.06494)

April 19, 2016 stat.AP
A maximum likelihood estimator for fusing the measurements in an inertial sensor array is presented. The maximum likelihood estimator is concentrated and an iterative solution method is presented for the resulting low-dimensional optimization problem. The Cram\'er-Rao bound for the corresponding measurement fusion problem is derived and used to assess the performance of the proposed method, as well as to analyze how the geometry of the array and sensor errors affect the accuracy of the measurement fusion. The angular velocity information gained from the accelerometers in the array is shown to be proportional to the square of the array dimension and to the square of the angular speed. In our simulations the proposed fusion method attains the Cram\'er-Rao bound and outperforms the current state-of-the-art method for measurement fusion in accelerometer arrays. Further, in contrast to the state-of-the-art method that requires a 3D array to work, the proposed method also works for 2D arrays. The theoretical findings are compared to results from real-world experiments with an in-house developed array that consists of 192 sensing elements.
• The Random Frequency Diverse Array: A New Antenna Structure for Uncoupled Direction-Range Indication in Active Sensing(1603.08188)

March 27, 2016 cs.IT, math.IT, stat.AP
In this paper, we propose a new type of array antenna, termed the Random Frequency Diverse Array (RFDA), for an uncoupled indication of target direction and range with low system complexity. In RFDA, each array element has a narrow bandwidth and a randomly assigned carrier frequency. The beampattern of the array is shown to be stochastic but thumbtack-like, and its stochastic characteristics, such as the mean, variance, and asymptotic distribution are derived analytically. Based on these two features, we propose two kinds of algorithms for signal processing. One is matched filtering, due to the beampattern's good characteristics. The other is compressive sensing, because the new approach can be regarded as a sparse and random sampling of target information in the spatial-frequency domain. Fundamental limits, such as the Cram\'er-Rao bound and the observing matrix's mutual coherence, are provided as performance guarantees of the new array structure. The features and performances of RFDA are verified with numerical results.
• On Clutter Ranks of Frequency Diverse Radar Waveforms(1603.08189)

March 27, 2016 cs.IT, math.IT, stat.AP
Frequency diverse (FD) radar waveforms are attractive in radar research and practice. By combining two typical FD waveforms, the frequency diverse array (FDA) and the stepped-frequency (SF) pulse train, we propose a general FD waveform model, termed the random frequency diverse multi-input-multi-output (RFD-MIMO) in this paper. The new model can be applied to specific FD waveforms by adapting parameters. Furthermore, by exploring the characteristics of the clutter covariance matrix, we provide an approach to evaluate the clutter rank of the RFD-MIMO radar, which can be adopted as a quantitive metric for the clutter suppression potentials of FD waveforms. Numerical simulations show the effectiveness of the clutter rank estimation method, and reveal helpful results for comparing the clutter suppression performance of different FD waveforms.
• Joint Sparse Recovery Method for Compressed Sensing with Structured Dictionary Mismatches(1309.0858)

July 24, 2014 cs.IT, math.IT
In traditional compressed sensing theory, the dictionary matrix is given a priori, whereas in real applications this matrix suffers from random noise and fluctuations. In this paper we consider a signal model where each column in the dictionary matrix is affected by a structured noise. This formulation is common in direction-of-arrival (DOA) estimation of off-grid targets, encountered in both radar systems and array processing. We propose to use joint sparse signal recovery to solve the compressed sensing problem with structured dictionary mismatches and also give an analytical performance bound on this joint sparse recovery. We show that, under mild conditions, the reconstruction error of the original sparse signal is bounded by both the sparsity and the noise level in the measurement model. Moreover, we implement fast first-order algorithms to speed up the computing process. Numerical examples demonstrate the good performance of the proposed algorithm, and also show that the joint-sparse recovery method yields a better reconstruction result than existing methods. By implementing the joint sparse recovery method, the accuracy and efficiency of DOA estimation are improved in both passive and active sensing cases.
• Smoothing and Decomposition for Analysis Sparse Recovery(1308.5000)

Jan. 14, 2014 cs.IT, math.IT, math.OC
We consider algorithms and recovery guarantees for the analysis sparse model in which the signal is sparse with respect to a highly coherent frame. We consider the use of a monotone version of the fast iterative shrinkage- thresholding algorithm (MFISTA) to solve the analysis sparse recovery problem. Since the proximal operator in MFISTA does not have a closed-form solution for the analysis model, it cannot be applied directly. Instead, we examine two alternatives based on smoothing and decomposition transformations that relax the original sparse recovery problem, and then implement MFISTA on the relaxed formulation. We refer to these two methods as smoothing-based and decomposition-based MFISTA. We analyze the convergence of both algorithms, and establish that smoothing- based MFISTA converges more rapidly when applied to general nonsmooth optimization problems. We then derive a performance bound on the reconstruction error using these techniques. The bound proves that our methods can recover a signal sparse in a redundant tight frame when the measurement matrix satisfies a properly adapted restricted isometry property. Numerical examples demonstrate the performance of our methods and show that smoothing-based MFISTA converges faster than the decomposition-based alternative in real applications, such as MRI image reconstruction.
• GPatt: Fast Multidimensional Pattern Extrapolation with Gaussian Processes(1310.5288)

Dec. 31, 2013 cs.AI, stat.ME, cs.LG, stat.ML
Gaussian processes are typically used for smoothing and interpolation on small datasets. We introduce a new Bayesian nonparametric framework -- GPatt -- enabling automatic pattern extrapolation with Gaussian processes on large multidimensional datasets. GPatt unifies and extends highly expressive kernels and fast exact inference techniques. Without human intervention -- no hand crafting of kernel features, and no sophisticated initialisation procedures -- we show that GPatt can solve large scale pattern extrapolation, inpainting, and kernel discovery problems, including a problem with 383400 training points. We find that GPatt significantly outperforms popular alternative scalable Gaussian process methods in speed and accuracy. Moreover, we discover profound differences between each of these methods, suggesting expressive kernels, nonparametric representations, and exact inference are useful for modelling large scale multidimensional patterns.
• Direction of Arrival Estimation Using Co-prime Arrays: A Super Resolution Viewpoint(1312.7793)

Dec. 30, 2013 cs.IT, math.IT
We consider the problem of direction of arrival (DOA) estimation using a newly proposed structure of non-uniform linear arrays, referred to as co-prime arrays, in this paper. By exploiting the second order statistical information of the received signals, co-prime arrays exhibit O(MN) degrees of freedom with only M + N sensors. A sparsity based recovery method is proposed to fully utilize these degrees of freedom. Unlike traditional sparse recovery methods, the proposed method is based on the developing theory of super resolution, which considers a continuous range of possible sources instead of discretizing this range into a discrete grid. With this approach, off-grid effects inherited in traditional sparse recovery can be neglected, thus improving the accuracy of DOA estimation. In this paper we show that in the noiseless case one can theoretically detect up to M N sources with only 2M + N sensors. The noise 2 statistics of co-prime arrays are also analyzed to demonstrate the robustness of the proposed optimization scheme. A source number detection method is presented based on the spectrum reconstructed from the sparse method. By extensive numerical examples, we show the superiority of the proposed method in terms of DOA estimation accuracy, degrees of freedom, and resolution ability compared with previous methods, such as MUSIC with spatial smoothing and the discrete sparse recovery method.
• Joint Optimization of Hybrid Energy Storage and Generation Capacity with Renewable Energy(1309.5832)

Sept. 23, 2013 math.OC
In an isolated power grid or a micro-grid with a small carbon footprint, the penetration of renewable energy is usually high. In such power grids, energy storage is important to guarantee an uninterrupted and stable power supply for end users. Different types of energy storage have different characteristics, including their round-trip efficiency, power and energy rating, energy loss over time, and investment and maintenance costs. In addition, the load characteristics and availability of different types of renewable energy sources vary in different geographic regions and at different times of year. Therefore joint capacity optimization for multiple types of energy storage and generation is important when designing this type of power systems. In this paper, we formulate a cost minimization problem for storage and generation planning, considering both the initial investment cost and operational/maintenance cost, and propose a distributed optimization framework to overcome the difficulty brought about by the large size of the optimization problem. The results will help in making decisions on energy storage and generation capacity planning in future decentralized power grids with high renewable penetrations.
• Distributed Optimization via Adaptive Regularization for Large Problems with Separable Constraints(1211.7309)

Nov. 30, 2012 cs.DC, math.OC
Many practical applications require solving an optimization over large and high-dimensional data sets, which makes these problems hard to solve and prohibitively time consuming. In this paper, we propose a parallel distributed algorithm that uses an adaptive regularizer (PDAR) to solve a joint optimization problem with separable constraints. The regularizer is adaptive and depends on the step size between iterations and the iteration number. We show theoretical converge of our algorithm to an optimal solution, and use a multi-agent three-bin resource allocation example to illustrate the effectiveness of the proposed algorithm. Numerical simulations show that our algorithm converges to the same optimal solution as other distributed methods, with significantly reduced computational time.
• The Stability of Low-Rank Matrix Reconstruction: a Constrained Singular Value View(1006.4088)

Sept. 7, 2012 cs.IT, math.IT
The stability of low-rank matrix reconstruction with respect to noise is investigated in this paper. The $\ell_*$-constrained minimal singular value ($\ell_*$-CMSV) of the measurement operator is shown to determine the recovery performance of nuclear norm minimization based algorithms. Compared with the stability results using the matrix restricted isometry constant, the performance bounds established using $\ell_*$-CMSV are more concise, and their derivations are less complex. Isotropic and subgaussian measurement operators are shown to have $\ell_*$-CMSVs bounded away from zero with high probability, as long as the number of measurements is relatively large. The $\ell_*$-CMSV for correlated Gaussian operators are also analyzed and used to illustrate the advantage of $\ell_*$-CMSV compared with the matrix restricted isometry constant. We also provide a fixed point characterization of $\ell_*$-CMSV that is potentially useful for its computation.
• Fixed point theory and semidefinite programming for computable performance analysis of block-sparsity recovery(1110.1078)

Oct. 5, 2011 math.NA, cs.IT, math.IT
In this paper, we employ fixed point theory and semidefinite programming to compute the performance bounds on convex block-sparsity recovery algorithms. As a prerequisite for optimal sensing matrix design, a computable performance bound would open doors for wide applications in sensor arrays, radar, DNA microarrays, and many other areas where block-sparsity arises naturally. We define a family of goodness measures for arbitrary sensing matrices as the optimal values of certain optimization problems. The reconstruction errors of convex recovery algorithms are bounded in terms of these goodness measures. We demonstrate that as long as the number of measurements is relatively large, these goodness measures are bounded away from zero for a large class of random sensing matrices, a result parallel to the probabilistic analysis of the block restricted isometry property. As the primary contribution of this work, we associate the goodness measures with the fixed points of functions defined by a series of semidefinite programs. This relation with fixed point theory yields efficient algorithms with global convergence guarantees to compute the goodness measures.
• Verifiable and computable performance analysis of sparsity recovery(1102.4868)

Oct. 5, 2011 math.NA, cs.IT, math.IT
In this paper, we develop verifiable and computable performance analysis of sparsity recovery. We define a family of goodness measures for arbitrary sensing matrices as a set of optimization problems, and design algorithms with a theoretical global convergence guarantee to compute these goodness measures. The proposed algorithms solve a series of second-order cone programs, or linear programs. As a by-product, we implement an efficient algorithm to verify a sufficient condition for exact sparsity recovery in the noise-free case. We derive performance bounds on the recovery errors in terms of these goodness measures. We also analytically demonstrate that the developed goodness measures are non-degenerate for a large class of random sensing matrices, as long as the number of measurements is relatively large. Numerical experiments show that, compared with the restricted isometry based performance bounds, our error bounds apply to a wider range of problems and are tighter, when the sparsity levels of the signals are relatively low.
• Performance Analysis of Sparse Recovery Based on Constrained Minimal Singular Values(1004.4222)

Feb. 24, 2011 cs.IT, math.IT
The stability of sparse signal reconstruction is investigated in this paper. We design efficient algorithms to verify the sufficient condition for unique $\ell_1$ sparse recovery. One of our algorithm produces comparable results with the state-of-the-art technique and performs orders of magnitude faster. We show that the $\ell_1$-constrained minimal singular value ($\ell_1$-CMSV) of the measurement matrix determines, in a very concise manner, the recovery performance of $\ell_1$-based algorithms such as the Basis Pursuit, the Dantzig selector, and the LASSO estimator. Compared with performance analysis involving the Restricted Isometry Constant, the arguments in this paper are much less complicated and provide more intuition on the stability of sparse signal recovery. We show also that, with high probability, the subgaussian ensemble generates measurement matrices with $\ell_1$-CMSVs bounded away from zero, as long as the number of measurements is relatively large. To compute the $\ell_1$-CMSV and its lower bound, we design two algorithms based on the interior point algorithm and the semi-definite relaxation.
• Performance analysis for sparse support recovery(0908.0744)

Nov. 5, 2009 cs.IT, math.IT
The performance of estimating the common support for jointly sparse signals based on their projections onto lower-dimensional space is analyzed. Support recovery is formulated as a multiple-hypothesis testing problem. Both upper and lower bounds on the probability of error are derived for general measurement matrices, by using the Chernoff bound and Fano's inequality, respectively. The upper bound shows that the performance is determined by a quantity measuring the measurement matrix incoherence, while the lower bound reveals the importance of the total measurement gain. The lower bound is applied to derive the minimal number of samples needed for accurate direction-of-arrival (DOA) estimation for a sparse representation based algorithm. When applied to Gaussian measurement ensembles, these bounds give necessary and sufficient conditions for a vanishing probability of error for majority realizations of the measurement matrix. Our results offer surprising insights into sparse signal recovery. For example, as far as support recovery is concerned, the well-known bound in Compressive Sensing with the Gaussian measurement matrix is generally not sufficient unless the noise level is low. Our study provides an alternative performance measure, one that is natural and important in practice, for signal recovery in Compressive Sensing and other application areas exploiting signal sparsity.