Search

An important problem in space-time adaptive detection is the estimation of the large p-by-p interference covariance matrix from training signals. When the number of training signals n is greater than 2p, existing estimators are generally considered to be adequate, as demonstrated by fixed-dimensional asymptotics. But in the low-sample-support regime (n < 2p or even n < p) fixed-dimensional asymptotics are no longer applicable. The remedy undertaken in this paper is to consider the "large dimensional limit" in which n and p go to infinity together. In this asymptotic regime, a new type of estimator is defined (Definition 2), shown to exist (Theorem 1), and shown to be detection-theoretically ideal (Theorem 2). Further, asymptotic conditional detection and false-alarm rates of filters formed from this type of estimator are characterized (Theorems 3 and 4) and shown to depend only on data that is given, even for non-Gaussian interference statistics. The paper concludes with several Monte Carlo simulations that compare the performance of the estimator in Theorem 1 to the predictions of Theorems 2-4, showing in particular higher detection probability than Steiner and Gerlach's Fast Maximum Likelihood estimator., 13 pages, 3 figures

This paper deals with an extension of Papoulis’ generalized sampling expansion (GSE) of bandlimited signals to a case where a white noise, filtered to the signal's band, is added before sampling. We look for the best sampling scheme that maximizes the capacity or minimizes the mean-squared error (MSE) of the sampled channel between the input signal and the $ M$ sampled outputs signals, e.g. channels. Due to the noise it is beneficial to sample at a total rate higher than Nyquist, yet there is no gain in sampling each signal above Nyquist; thus the total rate considered, normalized by Nyquist rate, is between 1 to $M$ . To avoid preference to any channel, the paper assumes that the channels are composed of all-pass linear time-invariant (LTI) systems. For the case where the total normalized rate is between $ M-1$ and $ M$ , we show that the best scheme samples $ M-1$ outputs at Nyquist rate and the last output at the remaining rate. Surprisingly, equal sampling is suboptimal in general, but when there is an integer relation between $ M$ and the total normalized rate, equal sampling achieves the optimal performance. We also make a conjecture on other rates that the best scheme either samples some channels at Nyquist and one another channel at the remaining rate, or sample the channels equally. This conjecture is supported by simulation for $M\leq 5$ . Finally, we discuss the relation between maximizing the capacity and minimizing the MSE.

This paper develops a new mathematical framework for denoising in blind two-dimensional (2D) super-resolution upon using the atomic norm. The framework denoises a signal that consists of a weighted sum of an unknown number of time-delayed and frequency-shifted unknown waveforms from its noisy measurements. Moreover, the framework also provides an approach for estimating the unknown parameters in the signal. We prove that when the number of the observed samples satisfies certain lower bound that is a function of the system parameters, we can estimate the noise-free signal, with very high accuracy, upon solving a regularized least-squares atomic norm minimization problem. We derive the theoretical mean-squared error of the estimator, and we show that it depends on the noise variance, the number of unknown waveforms, the number of samples, and the dimension of the low-dimensional space where the unknown waveforms lie. Finally, we verify the theoretical findings of the paper by using extensive simulation experiments.

In this paper we study the matrix completion problem: Suppose $X \in {\mathbb R}^{n_r \times n_c}$ is unknown except for a known upper bound $r$ on its rank. By measuring a small number $m \ll n_r n_c$ of elements of $X$, is it possible to recover $X$ exactly with noise-free measurements, or to construct a good approximation of $X$ with noisy measurements? Existing solutions to these problems involve sampling the elements uniformly and at random, and can guarantee exact recovery of the unknown matrix only with high probability. In this paper, we present a \textit{deterministic} sampling method for matrix completion. We achieve this by choosing the sampling set as the edge set of an asymmetric Ramanujan bigraph, and constrained nuclear norm minimization is the recovery method. Specifically, we derive sufficient conditions under which the unknown matrix is completed exactly with noise-free measurements, and is approximately completed with noisy measurements, which we call "stable" completion. The conditions derived here are only sufficient and more restrictive than random sampling. To study how close they are to being necessary, we conducted numerical simulations on randomly generated low rank matrices, using the LPS families of Ramanujan graphs. These simulations demonstrate two facts: (i) In order to achieve exact completion, it appears sufficient to choose the degree $d$ of the Ramanujan graph to be $\geq 3r$. (ii) There is a "phase transition," whereby the likelihood of success suddenly drops from 100\% to 0\% if the rank is increased by just one or two beyond a critical value. The phase transition phenomenon is well-known and well-studied in vector recovery using $\ell_1$-norm minimization. However, it is less studied in matrix completion and nuclear norm minimization, and not much understood., The original submission 1908.00963 has been split into two parts. The replacement submission is Part-1 of the revised version. Part-2 can also be found on arXiv

The practical application of a new class of coprime arrays based on the Chinese remainder theorem (CRT) over quadratic fields is presented in this paper. The proposed CRT arrays are constructed by ideal lattices embedded from coprime quadratic integers. The geometrical constructions and theoretical foundations were discussed in the accompanying paper in great detail, while this paper focuses on aspects of the application of the proposed arrays in two-dimensional (2D) remote sensing. A generalization of CRT arrays based on two or more pairwise coprime ideal lattices is proposed with closed-form expressions on sensor locations, the total number of sensors and the achievable DOF. The issues pertaining to the coprimality of any two quadratic integers are also addressed to explore all possible ideal lattices. Exploiting the symmetry of lattices, sensor reduction methods are discussed with the coarray remaining intact for economic maximization. In order to extend conventional angle estimation techniques based on uniformly distributed arrays to the method that can exploit any coarray configurations based on lattices, this paper introduces a hexagon-to-rectangular transformation to 2D spatial smoothing, providing the possibility of finding more compact sensor arrays. Examples are provided to verify the feasibility of the proposed methods., 13 pages, 15 figures

Estimation of multiple common remainders from a sequence of erroneous residue sets is an important step for the robust generalized Chinese Remainder Theorem (CRT). This paper considers the problem of how to estimate the two common remainders from their residue sets modulo a set of moduli. To measure the errors properly under the modular operation, we introduce two type circular distances. Based on these circular distances, two estimation methods are proposed by properly grouping the erroneous remainders into two ordered clusters. Both of the two methods perform better with lower computational complexities than the existing methods. In this paper, theoretical analysis as well as analytical results for the two proposed methods are obtained. For the first method, the two optimal estimates are proved to be in a finite set with no more than $L$ candidates, where $L$ is the number of the given moduli. The second method have closed forms. Simulation results show that the two proposed methods have nearly the same performance. These optimal estimates can improve the performance of the robust generalized CRT significantly.

Signal processing applications of semidefinite optimization are often rooted in sum-of-squares representations of nonnegative trigonometric polynomials. Interior-point solvers for semidefinite optimization can handle constraints of this form with a per-iteration-complexity that is cubic in the degree of the trigonometric polynomial. The purpose of this paper is to discuss first-order methods with a lower complexity per iteration. The methods are based on generalized proximal operators defined in terms of the Itakura–Saito distance. This is the Bregman distance defined by the negative entropy function. The choice for the Itakura–Saito distance is motivated by the fact that the associated generalized projection on the set of normalized nonnegative trigonometric polynomials can be computed at a cost that is roughly quadratic in the degree of the polynomial. The generalized projection is the key operation in generalized proximal first-order methods that use Bregman distances instead of the squared Euclidean distance. The paper includes numerical results with Auslender and Teboulle's accelerated proximal gradient method for Bregman distances.

How accurately can one estimate a deterministic parameter subject to other unknown deterministic model nuisance parameters? The most popular answer to this question is given by the Cramer–Rao bound (CRB). The main assumption behind the derivation of the CRB is local unbiased estimation of all model parameters. The foundations of this paper rely on doubting this assumption. Generally, in multivariate parameter estimation, each parameter in its turn can be treated as a single parameter of interest, whereas the other model parameters are treated as nuisance, as their misknowledge interferes with the estimation of the parameter of interest. This approach is utilized in this paper to provide a fresh look at deterministic parameter estimation. A new Cramer–Rao (CR) type bound is derived without assuming unbiased estimation of the nuisance parameters. Rather than that, we apply Lehmann's concept of unbiasedness for a risk that measures the distance between the estimator and the locally best unbiased estimator, which assumes perfect knowledge of the nuisance parameters. The proposed risk-unbiased CRB (RUCRB) is proven to be asymptotically attainable by the maximum likelihood estimator while being tighter than the conventional CRB. Furthermore, simulations verify the asymptotic achievability of the RUCRB by the maximum likelihood estimator for an array processing problem.

This paper provides new probabilistic guarantees for recovering the common support of jointly sparse vectors in multiple measurement vector (MMV) models. In recent times, Bayesian approaches for sparse signal recovery (such as sparse Bayesian learning and correlation-aware LASSO) have shown preliminary evidence that under appropriate conditions (such as access to ideal covariance matrix of the measurements or certain restrictive orthogonality condition on the signals), it is possible to recover supports of size ( $K$ ) larger than the dimension ( $M$ ) of each measurement vector. However, no results exist that characterize the probability with which this can be achieved for a finite number of measurement vectors ( $L$ ). This paper bridges this gap by formulating the support recovery problem in terms of a multiple hypothesis testing framework. Chernoff-type upper bounds on the probability of error are established, and new sufficient conditions are derived that guarantee its exponential decay with respect to $L$ even when $K=O(M^2)$ . Our sufficient conditions are based on the properties of the so-called Khatri–Rao product of the measurement matrix and reveal the importance of a sampler design. Negative results are also established indicating that when $K$ exceeds a certain threshold (in terms of $M$ ), there will exist a class of measurement matrices for which any support recovery algorithm will fail. Using results from the geometric probability, we characterize the probability with which a randomly generated measurement matrix will belong to this class and show that this probability tends to 1 asymptotically in the size ( $N$ ) of the sparse vectors.

In this paper, linearly constrained and robust $\ell _{\infty }$ -norm beamforming techniques are proposed for non-Gaussian signals. A conventional approach for $\ell _{\infty }$ -minimization needs to solve a linear programming (LP) or second-order cone programming (SOCP). However, this strategy is computationally prohibitive for “big data” because the existing algorithms for LP or SOCP, such as simplex method or interior point method, can only solve small- or medium-scale problems. In this paper, the alternating direction method of multipliers (ADMM) is devised for large-scale $\ell _{\infty }$ -beamforming problems, where the core subproblems can be formulated concisely as a linearly or second-order cone constrained least squares and the proximity operator of the $\ell _{\infty }$ -norm in each iteration. Remarkably, a linear-time complexity algorithm is devised that efficiently computes the $\ell _{\infty }$ -norm proximity operator. Simulation results verify the high efficiency of the ADMM and the superiority of the $\ell _{\infty }$ -norm beamforming techniques over several representative beamformers, indicating that its performance can approach the optimal upper bound.

Accurately monitoring the system's operating point is central to the reliable and economic operation of an electric power grid. Power system state estimation (PSSE) aims to obtain complete voltage magnitude and angle information at each bus given a number of system variables at selected buses and lines. Power flow analysis is a special case of PSSE, and amounts to solving a set of noise-free power flow equations. Physical laws dictate quadratic relationships between available quantities and unknown voltages, rendering general instances of power flow and PSSE nonconvex and NP-hard. Past approaches are largely based on gradient-type iterative procedures or semidefinite relaxation (SDR). Due to nonconvexity, the solution obtained via gradient-type schemes depends on initialization, while SDR methods do not perform as desired in challenging scenarios. This paper puts forth novel \emph{feasible point pursuit} (FPP)-based solvers for power flow and PSSE, which iteratively seek feasible solutions for a nonconvex quadratically constrained quadratic programming (QCQP) reformulation of the weighted least-squares (WLS) problem. Relative to the prior art, the developed solvers offer superior performance at the cost of higher complexity. Furthermore, they converge to a stationary point of the WLS problem. As a baseline for comparing different estimators, the Cram{\' e}r-Rao lower bound (CRLB) is derived for the fundamental PSSE problem in this paper. Judicious numerical tests on several IEEE benchmark systems showcase markedly improved performance of our FPP-based solvers for both power flow and PSSE tasks over popular WLS-based Gauss-Newton iterations and SDR approaches., Comment: 2 figures, 9 pages

In this paper, we analyze the effect of nonuniform array configurations on adaptive beamforming for enhanced signal-to-interference-plus-noise ratio (SINR). The array is configured using a given number of antennas or through a selection of subset of antennas from a larger available set, leading to a sparse array in both cases. The bounds on the highest achievable SINR for a given number of antennas are formulated and used to offer new insights into open-loop adaptive beamforming. The upper and lower bounds underscore the role of array configurations in optimizing performance for interference-free and interference-active environments, respectively. This paper considers the general case of multiple sources and interferences in the field of view. We formulate three angles, namely eigenspace angle, conventional angle, and minimum canonical angle for characterizing spatial separation between the source and interference subspaces, which represent performance loss incurred by interference nulling. Three sparse array design methods, incorporating these angles, are proposed. Simulation examples confirm the role of subspace angles in optimum beamforming and validate the utility of antenna selection algorithms for sparse array design.

A coprime sensor array (CSA) interleaves two undersampled uniform linear arrays with coprime undersampling factors and has recently found broad applications in signal detection and estimation. CSAs commonly use the product processor by multiplying the scanned responses of two colinear subarrays to estimate the spatial power spectral density (PSD) of the received signal. This paper proposes a new CSA processor, the CSAmin processor, which chooses the minimum between the two CSA subarray periodograms at each bearing to estimate the spatial PSD. The proposed CSAmin processor resolves the CSA subarray spatial aliasing equally well as the product processor. For an extended aperture CSA, the CSAmin reduces the peak sidelobe height and total sidelobe area over the product processor for the same CSA geometry. Moreover, unlike the PSD estimate from the product processor, the PSD estimate from the CSAmin is guaranteed to be positive semidefinite. This paper derives the probability density function, the complementary cumulative distribution function (CCDF, or tail distribution), and the first two moments of the CSAmin PSD estimator in closed form for Gaussian sources in white Gaussian noise. Numerical simulations verify the derived CSAmin statistics and demonstrate that the CSAmin improves the performance over the product processor in detecting narrowband Gaussian sources in the presence of loud interferers and noise. The CSAmin spatial PSD estimate achieves lower variance than the product processor estimate, and keeps the PSD estimate unbiased for white Gaussian processes and asymptotically unbiased for nonwhite Gaussian processes.

This paper presents an extension of the integrated time-chirp rate analysis technique, known as the parameterized centroid frequency-chirp rate distribution (PCFCRD), for noisy multicomponent linear frequency modulated signals analysis. The PCFCRD is based on a newly defined correlation function and its auto term accumulation is two-dimensionally coherent. The principle, cross term characteristic, implementation, properties, parameter selection criterion, antinoise performance, and estimation accuracy are analyzed for the PCFCRD. In this paper, comparisons with the coherently integrated cubic phase function, maximum likelihood method, and Lv's distribution are performed. With mathematic analyses and numerical simulations, we demonstrate that the PCFCRD outperforms these three representative counterparts. Further, by combining with analyses of the PCFCRD, several unclear mechanisms of the constant delay introduction are mathematically interpreted, especially quantitative influences on the chirp rate resolution and theoretical antinoise performance.

We propose an approximation method for thresholding of singular values using Chebyshev polynomial approximation (CPA). Many signal processing problems require iterative application of singular value decomposition (SVD) for minimizing the rank of a given data matrix with other cost functions and/or constraints, which is called matrix rank minimization. In matrix rank minimization, singular values of a matrix are shrunk by hard-thresholding, soft-thresholding, or weighted soft-thresholding. However, the computational cost of SVD is generally too expensive to handle high dimensional signals such as images; hence, in this case, matrix rank minimization requires enormous computation time. In this paper, we leverage CPA to (approximately) manipulate singular values without computing singular values and vectors. The thresholding of singular values is expressed by a multiplication of certain matrices, which is derived from a characteristic of CPA. The multiplication is also efficiently computed using the sparsity of signals. As a result, the computational cost is significantly reduced. Experimental results suggest the effectiveness of our method through several image processing applications based on matrix rank minimization with nuclear norm relaxation in terms of computation time and approximation precision., Comment: This is a journal paper

In this paper, we propose a widely linear reproducing kernel Hilbert space (WL-RKHS) for nonlinear regression with complex-valued signals. Our approach is a nonlinear extension of WL signal processing that has been proven to be more versatile than linear systems for dealing with complex-value signals. To be able to use the WL concept in kernel methods, we need to introduce a pseudo-kernel to complement the standard kernel in RKHS, which is not defined in previous RKHS approaches in the existing literature. In this paper, we present WL-RKHS, its properties, and the kernel and pseudo-kernel designs. We illustrate the need of the pseudo-kernel with simply verifiable examples that allow understanding the intuitions behind this kernel. We conclude this paper, showing that in the all-relevant nonlinear equalization problem the pseudo-kernel plays a significant role and previous approaches that do not rely on this kernel clearly underperform.

International audience; This paper addresses the problem of direction of arrival (DOA) estimation and blind source separation (BSS) for non-stationary signals in the underdetermined case. These two problems are strongly related to the mixing matrix estimation problem. To deal with the non-stationary characteristics of signals, this study uses high-resolution quadratic time-frequency distributions (TFDs) to reduce the cross-terms while keeping a good resolution for the construction of the spatial TFDs (STFDs). The main contributions of this paper are (1) the formulation of a statistical test for the noise thresholding step to improve robustness and avoid the use of empirical parameters; this test performs multisource selection of the time-frequency points where the signal of interest is present; (2) the use of an algorithm, based on image processing methods, which performs an auto-source selection for mixing matrix estimation. The paper presents results on simulated signals that demonstrate an improvement of 10 dB in terms of normalized mean square error for BSS and 7% in terms of relative error for DOA estimation over standard methods.

A number of important problems in engineering can be formulated as non-convex quadratically constrained quadratic programming (QCQP). The general QCQP problem is NP-Hard. In this paper, we consider a class of non-convex QCQP problems that are expressible as the maximization of the point-wise minimum of homogeneous convex quadratics over a “simple” convex set. Existing approximation strategies for such problems are generally incapable of achieving favorable performance-complexity tradeoffs. They are either characterized by good performance but high complexity and lack of scalability, or low complexity but relatively inferior performance. This paper focuses on bridging this gap by developing high performance, low complexity successive non-smooth convex approximation algorithms for problems in this class. Exploiting the structure inherent in each subproblem, specialized first-order methods are used to efficiently compute solutions. Multicast beamforming is considered as an application example to showcase the effectiveness of the proposed algorithms, which achieve a very favorable performance-complexity tradeoff relative to the existing state of the art.

This paper deals with near-optimal spectrum sensing of orthogonal frequency division multiplexing (OFDM) signals to achieve reliable detection at low signal-to-noise ratio (SNR). The likelihood ratio test (LRT), a simple hypothesis test , delivers the optimal performance, but it requires that the parameters involved in the test are known. Hence, the generalized likelihood ratio test (GLRT), a composite hypothesis test , has often been employed. However, GLRT-based detectors involve biased parameter estimation, which may lead to inferior performance. In this paper, with proper approximation, the LRT is reduced to a simpler form, which only requires the knowledge of noise power. Then a novel unbiased and consistent estimator of the noise power is developed. This estimator is combined with the approximate LRT, leading to an asymptotic simple hypothesis test (ASHT). Two ASHT-based detectors are presented for cases with and without time synchronization, and their theoretical performances are analyzed. Simulation results show that the ASHT-based detectors deliver performances very close to that of the optimal LRT, and significantly outperform the existing GLRT-based detectors. It is also shown that the ASHT-based detectors exhibit robustness against the influence of multipath channels.

This paper investigates the problem of distributed stochastic approximation in multiagent systems. The algorithm under study consists of two steps: A local stochastic approximation step and a diffusion step, which drives the network to a consensus. The diffusion step uses row-stochastic matrices to weight the network exchanges. As opposed to previous works, exchange matrices are not supposed to be doubly stochastic, and may also depend on the past estimate. We prove that nondoubly stochastic matrices generally influence the limit points of the algorithm. Nevertheless, the limit points are not affected by the choice of the matrices provided that the latter are doubly stochastic in expectation. This conclusion legitimates the use of broadcast-like diffusion protocols, which are easier to implement. Next, by means of a central limit theorem, we prove that doubly stochastic protocols perform asymptotically as well as centralized algorithms and we quantify the degradation caused by the use of nondoubly stochastic matrices. Throughout this paper, a special emphasis is put on the special case of distributed nonconvex optimization as an illustration of our results.

This paper concerns the sparse Bayesian learning (SBL) problem for group sparse signals. Group sparsity means that the signal coefficients can be divided into groups and that the entries in one group are simultaneously zero or nonzero. In SBL, each group is controlled by a hyperparameter, which is estimated by solving the marginal likelihood maximization (MLM) problem. MLM is used to maximize the marginal likelihood of a given hyper-parameter by fixing all others. The main contribution of this paper is to extend the fast marginal likelihood maximization (FMLM) method to the group sparsity case. The key process of realizing FMLM in the group sparsity case is solved by finding the roots of a polynomial. Hence, the local maximum of the marginal likelihood can be found exactly, and the final estimation is obtained more efficiently. Furthermore, most large matrix inverses involved in MLM are replaced with the eigenvalue decompositions of much smaller matrices, which substantially reduces the computational complexity. Numerical results with both simulated and real data demonstrate the excellent performance and relatively high computational efficiency of the proposed method.

The product of the scanned responses of two colinear interleaved arrays estimates the spatial power spectral density of the received signal. This estimate has mathematical structure similar to the classical periodogram and hence is called the generalized periodogram. The generalized periodogram includes sparse arrays such as coprime arrays and two level nested arrays. This paper derives the analytical expected value of the generalized periodogram output for any signal. The generalized periodogram expected value is the convolution of the true spectral density with a windowing function. This result reveals that the expected product spectrum is not guaranteed to be positive definite. The paper also derives the covariance function of the generalized periodogram for a white Gaussian process. Finally, the paper illustrates the implicit equivalence between the product spectrum and estimation of the correlation function from the products of appropriately spaced pairs of sensors.

This paper is concerned with the problem of low rank plus sparse matrix decomposition for big data. Conventional algorithms for matrix decomposition use the entire data to extract the low-rank and sparse components, and are based on optimization problems with complexity that scales with the dimension of the data, which limits their scalability. Furthermore, existing randomized approaches mostly rely on uniform random sampling, which is quite inefficient for many real world data matrices that exhibit additional structures (e.g. clustering). In this paper, a scalable subspace-pursuit approach that transforms the decomposition problem to a subspace learning problem is proposed. The decomposition is carried out using a small data sketch formed from sampled columns/rows. Even when the data is sampled uniformly at random, it is shown that the sufficient number of sampled columns/rows is roughly O(r\mu), where \mu is the coherency parameter and r the rank of the low rank component. In addition, adaptive sampling algorithms are proposed to address the problem of column/row sampling from structured data. We provide an analysis of the proposed method with adaptive sampling and show that adaptive sampling makes the required number of sampled columns/rows invariant to the distribution of the data. The proposed approach is amenable to online implementation and an online scheme is proposed., Comment: IEEE Transactions on Signal Processing

This paper concentrates on a robust transmit optimization problem for the multiuser multi-input single-output (MISO) downlink scenario and under inaccurate channel state information (CSI). This robust problem deals with a general-rank transmit covariance design, and it follows a safe rate-constrained formulation under spherically bounded CSI uncertainties. Curiously, simulation results in previous works suggested that the robust problem admits rank-one optimal transmit covariances in most cases. Such a numerical finding is appealing because transmission with rank-one covariances can be easily realized by single-stream transmit beamforming. This gives rise to a fundamentally important question, namely, whether we can theoretically identify conditions under which the robust problem admits a rank-one solution. In this paper, we identify one such condition. Simply speaking, we show that the robust problem is guaranteed to admit a rank-one solution if the CSI uncertainties are not too large and the multiuser channel is not too poorly conditioned. To establish the aforementioned condition, we develop a novel duality framework, through which an intimate relationship between the robust problem and a related maximin problem is revealed. Our condition involves only a simple expression with respect to the multiuser channel and other system parameters. In particular, unlike other sufficient rank-one conditions that have appeared in the literature, ours is verifiable. The application of our analysis framework to several other CSI uncertainty models is also discussed., To appear in IEEE Trans. Signal Process. This version combines the main manuscript and its accompanied supplementary report into one single article

A number of applications in engineering, social sciences, physics, and biology involve inference over networks. In this context, graph signals are widely encountered as descriptors of vertex attributes or features in graph-structured data. Estimating such signals in all vertices given noisy observations of their values on a subset of vertices has been extensively analyzed in the literature of signal processing on graphs (SPoG). This paper advocates kernel regression as a framework generalizing popular SPoG modeling and reconstruction and expanding their capabilities. Formulating signal reconstruction as a regression task on reproducing kernel Hilbert spaces of graph signals permeates benefits from statistical learning, offers fresh insights, and allows for estimators to leverage richer forms of prior information than existing alternatives. A number of SPoG notions such as bandlimitedness, graph filters, and the graph Fourier transform are naturally accommodated in the kernel framework. Additionally, this paper capitalizes on the so-called representer theorem to devise simpler versions of existing Thikhonov regularized estimators, and offers a novel probabilistic interpretation of kernel methods on graphs based on graphical models. Motivated by the challenges of selecting the bandwidth parameter in SPoG estimators or the kernel map in kernel-based methods, the present paper further proposes two multi-kernel approaches with complementary strengths. Whereas the first enables estimation of the unknown bandwidth of bandlimited signals, the second allows for efficient graph filter selection. Numerical tests with synthetic as well as real data demonstrate the merits of the proposed methods relative to state-of-the-art alternatives., Comment: Submitted May 2016

Signal processing on graphs finds applications in many areas. In recent years, renewed interest on this topic was kindled by two groups of researchers. Narang and Ortega constructed two-channel filter banks on bipartitie graphs described by Laplacians. Sandryhaila and Moura developed the theory of linear systems, filtering, and frequency responses for the case of graphs with arbitrary adjacency matrices, and showed applications in signal compression, prediction, etc. Inspired by these contributions, this paper extends classical multirate signal processing ideas to graphs. The graphs are assumed to be general with a possibly nonsymmetric and complex adjacency matrix. The paper revisits ideas, such as noble identities, aliasing, and polyphase decompositions in graph multirate systems. Drawing such a parallel to classical systems allows one to design filter banks with polynomial filters, with lower complexity than arbitrary graph filters. It is shown that the extension of classical multirate theory to graphs is nontrivial, and requires certain mathematical restrictions on the graph. Thus, classical noble identities cannot be taken for granted. Similarly, one cannot claim that the so-called delay chain system is a perfect reconstruction system (as in classical filter banks). It will also be shown that $M$ -partite extensions of the bipartite filter bank results will not work for $M$ -channel filter banks, but a more restrictive condition called $M$ -block cyclic property should be imposed. Such graphs are studied in detail. A detailed theory for $M$ -channel filter banks is developed in a companion paper.

One of the cornerstones of the field of signal processing on graphs are graph filters, direct analogs of classical filters, but intended for signals defined on graphs. This paper brings forth new insights on the distributed graph filtering problem. We design a family of autoregressive moving average (ARMA) recursions, which are able to approximate any desired graph frequency response, and give exact solutions for specific graph signal denoising and interpolation problems. The philosophy to design the ARMA coefficients independently from the underlying graph renders the ARMA graph filters suitable in static and, particularly, time-varying settings. The latter occur when the graph signal and/or graph topology are changing over time. We show that in case of a time-varying graph signal, our approach extends naturally to a two-dimensional filter, operating concurrently in the graph and regular time domain. We also derive the graph filter behavior, as well as sufficient conditions for filter stability when the graph and signal are time varying. The analytical and numerical results presented in this paper illustrate that ARMA graph filters are practically appealing for static and time-varying settings, as predicted by theoretical derivations.

This is Part II of a series of two papers where we address sequential estimation of wide-sense stationary autoregressive moving average (ARMA) state processes by particle filtering. In Part I, we considered a state-space model where the state was an ARMA process of known order and where the parameters of the process could be known or unknown. In this paper, we extend our work from Part I by considering the same type of models, with the added complexity that the ARMA processes are now of unknown order. Instead of working on a scheme that first tracks the state by operating with different assumed models, and then selects the best model by using a predefined criterion, we present a method that directly estimates the state without the need of knowing the model order. We derive the transition density of the state for unknown ARMA model order, and propose a particle filter based on that density and the empirical Bayesian methodology. We demonstrate the performance of the proposed method with computer simulations and compare it with the methods from Part I.

This paper addresses the issue of robust sparse recovery in compressive sensing (CS) in the presence of impulsive measurement noise. Recently, robust data-fitting models, such as $\ell _1$ -norm, Lorentzian-norm, and Huber penalty function, have been employed to replace the popular $\ell _2$ -norm loss model to gain more robust performance. In this paper, we propose a robust formulation for sparse recovery using the generalized $\ell _p$ -norm with $0\leq p as the metric for the residual error. To solve this formulation efficiently, we develop an alternating direction method (ADM) via incorporating the proximity operator of $\ell _p$ -norm functions into the framework of augmented Lagrangian methods. Furthermore, to derive a convergent method for the nonconvex case of $p 1, a smoothing strategy has been employed. The convergence conditions of the proposed algorithm have been analyzed for both the convex and nonconvex cases. The new algorithm has been compared with some state-of-the-art robust algorithms via numerical simulations to show its improved performance in highly impulsive noise.

In this paper, a novel model-based compressive sampling (CS) technique for natural images is proposed. Our algorithm integrates a universal hidden Markov tree (uHMT) model, which captures the relation among the sparse wavelet coefficients of images, into both sampling and recovery steps of CS. At the sampling step, we employ the uHMT model to devise a nonuniformly sparse measurement matrix $\boldsymbol{\Phi }_{\text{uHMT}}$ . In contrast to the conventional CS sampling matrices, such as dense Gaussian, Bernoulli or uniformly sparse matrices that are oblivious to the signal model and the correlation among the signal coefficients, the proposed $\boldsymbol{\Phi }_{\text{uHMT}}$ is designed based on the signal model and samples the coarser wavelet coefficients with higher probabilities and more sparse wavelet coefficients with lower probabilities. At the recovery step, we integrate the uHMT model into two state-of-the-art Bayesian CS recovery schemes. Our simulation results confirm the superiority of our proposed HMT model-based nonuniform compressive sampling and recovery , referred to as uHMT-NCS , over other model-based CS techniques that solely consider the signal model at the recovery step. This paper is distinguished from other model-based CS schemes in that we take a novel approach to simultaneously integrating the signal model into both CS sampling and recovery steps. We show that such integration greatly increases the performance of the CS recovery, which is equivalent to reducing the required number of samples for a given reconstruction quality.

This paper describes the adaptive detection of point-like targets in a Gaussian environment assuming a group symmetric structure for the interference covariance matrix. This special configuration enforces block-sparsity and permits splitting of the original observation space into lower-dimensional subspaces, each characterized by its own nuisance parameters. Hence, the Principle of Invariance is invoked to select decision rules enjoying some symmetry defined by a suitable group of transformations which leave the decision problem unaltered. All the invariant tests can be expressed as functions of a maximal invariant statistic whose derivation is among the key results of this paper. Finally, some common design criteria are applied to come up with adaptive architectures that share invariance, and their behavior is assessed to highlight the interplay between sample size and detection performance in comparison with conventional decision schemes.

This paper considers \emph{volume minimization} (VolMin)-based structured matrix factorization (SMF). VolMin is a factorization criterion that decomposes a given data matrix into a basis matrix times a structured coefficient matrix via finding the minimum-volume simplex that encloses all the columns of the data matrix. Recent work showed that VolMin guarantees the identifiability of the factor matrices under mild conditions that are realistic in a wide variety of applications. This paper focuses on both theoretical and practical aspects of VolMin. On the theory side, exact equivalence of two independently developed sufficient conditions for VolMin identifiability is proven here, thereby providing a more comprehensive understanding of this aspect of VolMin. On the algorithm side, computational complexity and sensitivity to outliers are two key challenges associated with real-world applications of VolMin. These are addressed here via a new VolMin algorithm that handles volume regularization in a computationally simple way, and automatically detects and {iteratively downweights} outliers, simultaneously. Simulations and real-data experiments using a remotely sensed hyperspectral image and the Reuters document corpus are employed to showcase the effectiveness of the proposed algorithm.

Blind gain and phase calibration (BGPC) is a structured bilinear inverse problem, which arises in many applications, including inverse rendering in computational relighting (albedo estimation with unknown lighting), blind phase and gain calibration in sensor array processing, and multichannel blind deconvolution. The fundamental question of the uniqueness of the solutions to such problems has been addressed only recently. In a previous paper, we proposed studying the identifiability in bilinear inverse problems up to transformation groups. In particular, we studied several special cases of blind gain and phase calibration, including the cases of subspace and joint sparsity models on the signals, and gave sufficient and necessary conditions for identifiability up to certain transformation groups. However, there were gaps between the sample complexities in the sufficient conditions and the necessary conditions. In this paper, under a mild assumption that the signals and models are generic, we bridge the gaps by deriving tight sufficient conditions with optimal sample complexities., 17 pages, 1 figure. arXiv admin note: text overlap with arXiv:1501.06120

Measuring the Time delay of Arrival (TDOA) between a set of sensors is the basic setup for many applications, such as localization or signal beamforming. This paper presents the set of TDOA matrices, which are built from noise-free TDOA measurements, not requiring knowledge of the sensor array geometry. We prove that TDOA matrices are rank-two and have a special SVD decomposition that leads to a compact linear parametric representation. Properties of TDOA matrices are applied in this paper to perform denoising, by finding the TDOA matrix closest to the matrix composed with noisy measurements. The paper shows that this problem admits a closed-form solution for TDOA measurements contaminated with Gaussian noise which extends to the case of having missing data. The paper also proposes a novel robust denoising method resistant to outliers, missing data and inspired in recent advances in robust low-rank estimation. Experiments in synthetic and real datasets show significant improvements of the proposed denoising algorithms in TDOA-based localization, both in terms of TDOA accuracy estimation and localization error.

This paper addresses the design of adaptive subspace matched filter (ASMF) detectors in the presence of a mismatch in the steering vector. These detectors are coined as adaptive in reference to the step of utilizing an estimate of the clutter covariance matrix using training data of signal-free observations. To estimate the clutter covariance matrix, we employ regularized covariance estimators that, by construction, force the eigenvalues of the covariance estimates to be greater than a positive scalar $\rho $ . While this feature is likely to increase the bias of the covariance estimate, it presents the advantage of improving its conditioning, thus making the regularization suitable for handling high-dimensional regimes. In this paper, we consider the setting of the regularization parameter and the threshold for ASMF detectors in both Gaussian and compound Gaussian clutters. In order to allow for a proper selection of these parameters, it is essential to analyze the false alarm and detection probabilities. For tractability, such a task is carried out under the asymptotic regime in which the number of observations and their dimensions grow simultaneously large, thereby allowing us to leverage existing results from random matrix theory. Simulation results are provided in order to illustrate the relevance of the proposed design strategy and to compare the performances of the proposed ASMF detectors versus adaptive normalized matched filter (ANMF) detectors under mismatch scenarios.

The stability problems of the least mean fourth (LMF) algorithm put a limitation on its tracking capability. The paper investigates the possibility of solving this problem via stabilization of the algorithm. The analysis is done for a Markov plant. It is found that the available stable normalized LMF (NLMF) algorithm has a tracking limitation for high signal-to-noise ratio. The paper presents a new stable NLMF algorithm that is free of this limitation. Mean-square stability of the algorithm is proved. Expressions are derived for the minimum steady-state mean square deviation (MSD) and the corresponding convergence time. The new algorithm outperforms the available stable NLMF algorithm in both the transient and steady states. The new algorithm is also compared with the NLMS algorithm when the adaptation parameter of each algorithm is set to the value that minimizes its steady-state MSD. For large initial MSD, the algorithm outperforms the NLMS algorithm, even for Gaussian noise. For small initial MSD, the algorithm outperforms the NLMS algorithm for sub-Gaussian noise, while the situation is opposite for Gaussian noise. Analytical results are supported by simulations.

Recently, several high-resolution parameter estimation algorithms have been developed to exploit the structure of strictly second-order (SO) non-circular (NC) signals. They achieve a higher estimation accuracy and can resolve up to twice as many signal sources compared to the traditional methods for arbitrary signals. In this paper, as a benchmark for these NC methods, we derive the closed-form deterministic R-D NC Cramer-Rao bound (NC CRB) for the multi-dimensional parameter estimation of strictly non-circular (rectilinear) signal sources. Assuming a separable centro-symmetric R-D array, we show that in some special cases, the deterministic R-D NC CRB reduces to the existing deterministic R-D CRB for arbitrary signals. This suggests that no gain from strictly non-circular sources (NC gain) can be achieved in these cases. For more general scenarios, finding an analytical expression of the NC gain for an arbitrary number of sources is very challenging. Thus, in this paper, we simplify the derived NC CRB and the existing CRB for the special case of two closely-spaced strictly non-circular sources captured by a uniform linear array (ULA). Subsequently, we use these simplified CRB expressions to analytically compute the maximum achievable asymptotic NC gain for the considered two source case. The resulting expression only depends on the various physical parameters and we find the conditions that provide the largest NC gain for two sources. Our analysis is supported by extensive simulation results., Comment: submitted to IEEE Transactions on Signal Processing, 13 pages, 4 figures

High SNR consistency of model order selection criteria in linear regression models has attracted a lot of attention in the signal processing community recently. It is now known that Exponentially Embedded Family, versions of Minimum Description Length etc. are high SNR consistent. However, a general framework for high SNR consistency in linear regression is still missing. This paper fills this gap by deriving necessary and sufficient conditions (NSCs) for model order selection criteria in both known and unknown noise variance situations to be high SNR consistent. Many popular model order selection criteria are proved to be high SNR consistent using these NSCs. We also provide a convergence rate analysis to discriminate between various high SNR consistent model order selection criteria. A direct application of model order selection techniques to the very important subset selection problem is computationally infeasible. This paper establish the high SNR consistency of an existing t-statistics based index ordering scheme that allows the conversion of a subset selection problem into a model order selection problem. Combining this index ordering with high SNR consistent model order selection criteria leads to a novel subset selection procedure (SSP) that is numerically shown to outperform existing high SNR consistent SSPs.

In array processing, mutual coupling between sensors has an adverse effect on the estimation of parameters (e.g., DOA). Sparse arrays such as nested arrays, coprime arrays, and minimum redundancy arrays (MRA) have reduced mutual coupling compared to uniform linear arrays (ULAs). These arrays also have a difference coarray with $O\left({N}^{2}\right)$ virtual elements, where $N$ is the number of physical sensors, and can therefore resolve $O\left({N}^{2}\right)$ uncorrelated source directions. But these well-known sparse arrays have disadvantages: MRAs do not have simple closed-form expressions for the array geometry; coprime arrays have holes in the coarray; and nested arrays contain a dense ULA in the physical array, resulting in significantly higher mutual coupling than coprime arrays and MRAs. In a companion paper, a sparse array configuration called the (second-order) super nested array was introduced, which has many of the advantages of these sparse arrays, while removing most of the disadvantages. Namely, the sensor locations are readily computed for any $N$ (unlike MRAs), and the difference coarray is exactly that of a nested array, and therefore hole-free. At the same time, the mutual coupling is reduced significantly (unlike nested arrays). In this paper, a generalization of super nested arrays is introduced, called the $Q$ th-order super nested array. This has all the properties of the second-order super nested array with the additional advantage that mutual coupling effects are further reduced for $Q > 2$ . Many theoretical properties are proved and simulations are included to demonstrate the superior performance of these arrays.

This paper considers the discrete sum rate maximization (DSRM) problem for beamformer optimization in multi-input single-output interference broadcast channels. In this problem, the achievable rates of the receivers are restricted to be taken from a set of finite discrete rate values, and such constraints arise from practical limitations with the modulation and coding schemes. Many existing studies consider sum rate maximization without the discrete rate constraints, and that may result in performance loss. In this paper, the DSRM problem is tackled via a convex approximation approach. Due to the discrete rate constraints, DSRM is a mixed-integer program. The idea of the proposed approach is to reformulate DSRM as a continuous, but still nonconvex, optimization problem. Then, appropriate convex approximations are applied. The advantage of the proposed approach is that the resulting approximate problems can be easily decomposed from a first-order optimization viewpoint. Utilizing this special feature, low-complexity and decentralized algorithms based on projected gradient are derived. Numerical results are used to show the efficiencies of the proposed algorithms in a multicell coordinated beamforming scenario. Also, this paper provides a proof for the convergence guarantee of one decentralized optimization strategy, namely, inexact maximum block improvement.

Designing and implementing systems as an interconnection of smaller subsystems is a common practice for modularity and standardization of components and design algorithms. Although not typically cast in this framework, many of these approaches can be viewed within the mathematical context of functional composition. This paper re-interprets and generalizes within the functional composition framework one such approach known as filter sharpening, i.e., interconnecting filter modules which have significant approximation error in order to obtain improved filter characteristics. More specifically, filter sharpening is approached by determining the composing polynomial to minimize the infinity-norm of the approximation error, utilizing the First Algorithm of Remez. This is applied both to sharpening for FIR, even-symmetric filters and for the more general case of subfilters that have complex-valued frequency responses including causal IIR filters and for continuous-time filters. Within the framework of functional composition, this paper also explores the use of functional decomposition to approximate a desired system as a composition of simpler functions based on a two-norm on the approximation error. Among the potential advantages of this decomposition is the ability for modular implementation in which the inner component of the functional decomposition represents the subfilters and the outer the interconnection.

In this paper, we address the issue of near-field source localization using spherical microphone array. The spherical array has been widely used for far-field source localization due to ease of array processing in spherical harmonics domain. Various methods for far-field source localization has been reformulated in spherical harmonics domain. However, near-field source localization that involves joint estimation of range and bearing of the sources has hitherto not been investigated. In this paper, the near-field data model is developed in spherical harmonics domain. In particular, three methods that jointly estimate the range and bearing of multiple sources in the spherical array framework are proposed. Two subspace-based methods called the Spherical Harmonic MUltiple SIgnal Classification (SH-MUSIC) and the Spherical Harmonics MUSIC-Group Delay (SH-MGD) for near-field source localization are first presented. In addition, a method for near-field source localization and beamforming using Spherical Harmonic MVDR (SH-MVDR) is also formulated. Formulation and analysis of Cramer–Rao bound for near-field sources is presented in spherical harmonics domain. Various source localization experiments were conducted on simulated and signal acquired over spherical microphone array in an anechoic chamber. Root-mean-square error and probability of resolution are utilized as measures to evaluate the proposed methods. The significance and practical application of the proposed methods is discussed using experiment on interference suppression. The near-field SH-MVDR beamforming is utilized in this context.

The generalized Hermitian eigenvalue problem (GHEP) is of great use in modern signal processing. Compared with other methods, neural network model based algorithms provide an efficient way to solve such problems online. Up to now, a class of neural network model based generalized feature extraction algorithms have been reported in the literature. However, most existing noncoupled algorithms suffer from the so-called speed-stability problem. In contrast, coupled learning algorithms estimate the generalized eigenvector and generalized eigenvalue simultaneously in coupled manners. Therefore they can solve the speed-stability problem and perform better than noncoupled algorithms. In this paper, we first propose a coupled generalized system, which is obtained by using the Newton’s method and a novel generalized information criterion. Then, based on this coupled generalized system, we successfully obtain two coupled algorithms with normalization steps for minor/principal generalized eigen-pairs extraction. And the technique of multiple generalized eigen-pairs extraction is also introduced in this paper. The convergence of the proposed algorithms is justified by deterministic discrete-time (DDT) approach, with the efficiency and feasibility validated by experimental results as well. Compared with similar work, the proposed algorithms have lower computational complexity, better numerical stability and higher estimation accuracy.

This paper proposes a novel method of estimating the Fourier transform (FT) of deterministic, continuous-time signals, from a finite number $N$ of their samples taken from a fixed-length observation window. It uses alias-free hybrid-stratified sampling to probe the processed signal at a mixture of deterministic and random time instants. The FT estimator, specifically designed to work with this sampling scheme, is unbiased, consistent and fast converging. It is shown that if the processed signal has continuous third derivative, then the estimator’s rate of uniform convergence in mean square is $N^{-5}$ . Therefore, in terms of frequency-independent upper bounds on the FT estimation error, the proposed approach significantly outperforms existing estimators that utilize alias-free sampling, such as total random, stratified sampling, and antithetical stratified whose rate of uniform convergence is $N^{-1}$ . It is proven here that $N^{-1}$ is a guaranteed minimum rate for all stratified-sampling-based estimators satisfying four weak conditions formulated in this paper. Owing to the alias-free nature of the sampling scheme, no constraints are imposed on the spectral support of the processed signal or the frequency ranges for which the Fourier Transform is estimated.

This paper considers the problem of cooperative localization in mobile networks. In static networks, node locations can be obtained from pairwise distance measurements using the classical multidimensional scaling (MDS) approach. This paper introduces a modified MDS framework that also incorporates relative velocity measurements if available in mobile networks. The proposed cost function is minimized via a low complexity majorization algorithm. A distributed variant of the proposed algorithm is also outlined for use in large resource-constrained multi-hop networks. The proposed algorithm incurs low computational and communication cost, and handles practical constraints such as missing measurements and variable node velocities. Simulation results corroborate the performance gains obtained by the proposed algorithm over state-of-the-art localization algorithms.

International audience; This paper addresses the problem of the clutter subspace projector estimation in the context of a disturbance composed of a low rank heterogeneous (Compound Gaussian) clutter and white Gaussian noise. In such a context, adaptive processing based on an estimated orthogonal projector onto the clutter subspace (instead of an estimated covariance matrix) requires less samples than classical methods. The clutter subspace estimate is usually derived from the eigenvalue decomposition of a covariance matrix estimate. However, it has been previously shown that a direct maximum likelihood estimator of the clutter subspace projector can be obtained for the considered context. In this paper, we derive two algorithms based on the block majorization-minimization framework to reach this estimator. These algorithms are shown to be computationally faster than the state of the art, with guaranteed convergence. Finally, the performance of the related estimators is illustrated on realistic Space Time Adaptive Processing for airborne radar simulations.

Impulsive processes frequently occur in many fields, such as radar, sonar, communications, audio and speech processing, and biomedical engineering. In this paper, we propose a nonconvex linear regression (NLR) based minimum dispersion beamforming technique for impulsive signals to achieve significant performance improvement over the conventional minimum variance beamformer. The proposed beamformer minimizes the $\ell_{p}$ -norm of the output with $p subject to a linear distortionless response constraint, resulting in a difficult nonconvex and nonsmooth optimization problem. The constrained optimization problem is first reduced to a multivariate linear regression via constraint elimination. As a major contribution of this paper, a coordinate descent algorithm (CDA) is devised for solving the resultant NLR problem of $\ell_{p}$ -minimization with $p at a computational complexity of ${\cal O}(MN^{2})$ , where $M$ is the number of sensors and $N$ is the sample size. At each inner iteration of the CDA, an efficient algorithm is designed to find the global minimum of each subproblem of univariate linear regression. The convergence of the CDA is analyzed. The NLR beamformer with a single constraint is further generalized to the case of multiple linear constraints, which is robust against model mismatch. Simulation results demonstrate the superior performance of nonconvex optimization based beamformer.