Search

Dirty paper coding (DPC) scheme is the capacity achieving transmission technique in multiuser MIMO downlink channels. As a suboptimal solution to DPC, successive zero-forcing DPC (SZF-DPC) has been proposed recently. The zero-interference constraint in designing the precoding matrices limits the number of supportable users. In this correspondence, we propose three low-complexity suboptimal user scheduling algorithms to exploit the multiuser diversity gain in SZF-DPC as the number of users grows. The first algorithm greedily maximizes the true sum rate. The second algorithm is based on eigenvalues. The third algorithm relies on the diagonal elements of the effective channel matrix since eigenvalues and diagonal entries of a Hermitian matrix have a strong relationship. Simulation results show that the proposed scheduling algorithms can obtain a significant fraction of sum rate of the optimal solution. Furthermore, the performance analysis is provided to prove that the proposed user selection algorithms can achieve the same asymptotic sum rate as that of DPC.

Achieving the boundary of the capacity region in the multiple-input multiple-output (MIMO) broadcast channel requires the use of dirty paper coding (DPC). As practical nearly optimum implementations of DPC are computationally complex, purely linear approaches are often used instead. However, in this case, the problem of maximizing a weighted sum rate constitutes a nonconvex and, in most cases, also a combinatorial optimization problem. In this paper, we present two heuristic nearly optimum algorithms with reduced computational complexity. For this purpose, a lower bound for the weighted sum rate under linear zero-forcing constraints is used. Based on this bound, both greedy algorithms successively allocate data streams to users. In each step, the user is determined that is given an additional data stream such that the increase in weighted sum rate becomes maximum. Thereby, the data stream allocations and filters obtained in the previous steps are kept fixed and only the filter corresponding to the additional data stream is optimized. The first algorithm determines the receive and transmit filters directly in the downlink. The other algorithm operates in the dual uplink, from which the downlink transmit and receive filters can be obtained via the general rate duality leading to nonzero-forcing in the downlink. Simulation results reveal marginal performance losses compared to more complex algorithms.

In this paper, we propose a generalized greedy (G-greedy) algorithm based on zero-forcing beamforming (ZFBF) for the multiple-input multiple-output (MIMO) broadcast channel. This algorithm serves as a general mathematical framework that includes a number of existing greedy user selection methods as its realizations. As previous results only give the scaling law of the sum rate of dirty paper coding (DPC), with the help of the G-greedy structure, we are able to obtain the exact limit of the DPC sum rate for a large number of users. We also prove that the difference between the sum rates obtained by G-greedy user selection and by DPC goes to zero as the number of users increases. In addition to this, we investigate one particular greedy user selection scheme called sequential water-filling (SWF). For this algorithm, a complexity reduction is achieved by an iterative procedure based on an LQ decomposition, which converts the calculation of the Moore-Penrose matrix inverse to one vector-matrix multiplication. A sufficient condition is given to prune the search space of this algorithm that results in further complexity reduction. With the help of the G-greedy algorithm, we prove that SWF achieves the full DPC sum rate for a large number of users. For a moderate number of users, simulation demonstrates that, compared with other user selection algorithms, SWF achieves a higher sum rate that is close to the maximal sum rate achievable by ZFBF with the same order of complexity.

This paper considers the transmitter optimization problem for a multiuser downlink channel with multiple transmit antennas at the base-station. In contrast to the conventional sum-power constraint on the transmit antennas, this paper adopts a more realistic per-antenna power constraint, because in practical implementations each antenna is equipped with its own power amplifier and is limited individually by the linearity of the amplifier. Assuming perfect channel knowledge at the transmitter, this paper investigates two different transmission schemes under the per-antenna power constraint: a minimum-power beamforming design for downlink channels with a single antenna at each remote user and a capacity-achieving transmitter design for downlink channels with multiple antennas at each remote user. It is shown that in both cases, the per-antenna downlink transmitter optimization problem may be transformed into a dual uplink problem with an uncertain noise. This generalizes previous uplink-downlink duality results and transforms the per-antenna transmitter optimization problem into an equivalent minimax optimization problem. Further, it is shown that various notions of uplink-downlink duality may be unified under a Lagrangian duality framework. This new interpretation of duality gives rise to efficient numerical optimization techniques for solving the downlink per-antenna transmitter optimization problem

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

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

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

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.

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

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.

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.

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.

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.

Reduced-rank adaptive processing (RRAP) has received considerable attention in recent years. One of the key problems with this technique is how to determine an appropriate dimension for the reduced-rank subspace. In this paper we study in detail four types of rank selection methods for the widely used RRAP approach-multistage Wiener filter (MWF). All of these methods have a computational complexity of order O(1), compared with other existing methods with an order of O(i) or even O(i 2 ) at the ith stage of the MWF. The main idea underlying these methods is to find a recursive algorithm to calculate the stopping criterion. The first two algorithms, based on the generalized discrepancy principle (GDP) and error estimation (EE) respectively, are fast versions of existing approaches. The last two algorithms, based on fast Ritz values estimation (RVE) and new information (NI) respectively, are new and proposed in this paper. In addition to requiring less computation, simulation results show that the proposed algorithms have a higher accuracy in adaptive beamforming applications for both narrowband and broadband signals.

How accurately can one estimate a random parameter subject to unknown deterministic nuisance parameters? The hybrid Cramer-Rao bound (HCRB) provides an answer to this question for a restricted class of estimators. The HCRB is the most popular performance bound on the mean-square-error (MSE) for random parameter estimation problems which involve deterministic parameters. The HCRB is useful when one is interested in both the random and the deterministic parameters and in the coupling between their estimation errors. This bound refers to locally weak-sense unbiased estimators with respect to (w.r.t.) the deterministic parameters. However, if these parameters are nuisance, it is unnecessary to restrict their estimation as unbiased. This paper is the first of a two-part study of Bayesian parameter estimation in the presence of deterministic nuisance parameters. It begins with a study on order relations between existing Cramer-Rao (CR)-type bounds of mean-unbiased Bayesian estimators. Then, a new CR-type bound is developed with no assumption of unbiasedness on the nuisance parameters. Alternatively, Lehmann’s concept of unbiasedness is employed rather than conventional mean-unbiasedness. It is imposed on a risk that measures the distance between the estimator and the minimum MSE (MMSE) estimator which assumes perfect knowledge of the nuisance parameters. In the succeeding paper, asymptotic performances of some Bayesian estimators with maximum likelihood based estimates for the nuisance parameters are investigated. The proposed risk-unbiased bound (RUB) is proved to be asymptotically achieved by the MMSE estimator with maximum likelihood estimates for the nuisance parameters, while the existing CR-type bounds are not necessarily achievable.

This paper proposes a decentralized algorithm for solving a consensus optimization problem defined in a static networked multi-agent system, where the local objective functions have the smooth+nonsmooth composite form. Examples of such problems include decentralized constrained quadratic programming and compressed sensing problems, as well as many regularization problems arising in inverse problems, signal processing, and machine learning, which have decentralized applications. This paper addresses the need for efficient decentralized algorithms that take advantages of proximal operations for the nonsmooth terms. We propose a proximal gradient exact first-order algorithm (PG-EXTRA) that utilizes the composite structure and has the best known convergence rate. It is a nontrivial extension to the recent algorithm EXTRA. At each iteration, each agent locally computes a gradient of the smooth part of its objective and a proximal map of the nonsmooth part, as well as exchanges information with its neighbors. The algorithm is “exact” in the sense that an exact consensus minimizer can be obtained with a fixed step size, whereas most previous methods must use diminishing step sizes. When the smooth part has Lipschitz gradients, PG-EXTRA has an ergodic convergence rate of $O\left({1\over k}\right)$ in terms of the first-order optimality residual. When the smooth part vanishes, PG-EXTRA reduces to P-EXTRA, an algorithm without the gradients (so no “G” in the name), which has a slightly improved convergence rate at $o\left({1\over k}\right)$ in a standard (non-ergodic) sense. Numerical experiments demonstrate effectiveness of PG-EXTRA and validate our convergence results

This paper proposes a new framework for the design of transmit and receive beamformers for interference alignment (IA) without symbol extensions in multi-antenna cellular networks. We consider IA in a $G$ cell network with $K$ users/cell, $N$ antennas at each base station (BS) and $M$ antennas at each user. The proposed framework is developed by recasting the conditions for IA as two sets of rank constraints, one on the rank of interference matrices, and the other on the transmit beamformers in the uplink. The interference matrix consists of all the interfering vectors received at a BS from the out-of-cell users in the uplink. Using these conditions and the crucial observation that the rank of interference matrices under alignment can be determined beforehand, this paper develops two sets of algorithms for IA. The first part of this paper develops rank minimization algorithms for IA by iteratively minimizing a weighted matrix norm of the interference matrix. Different choices of matrix norms lead to reweighted nuclear norm minimization (RNNM) or reweighted Frobenius norm minimization (RFNM) algorithms with significantly different per-iteration complexities. Alternately, the second part of this paper devises an alternating minimization (AM) algorithm where the rank-deficient interference matrices are expressed as a product of two lower-dimensional matrices that are then alternately optimized. Simulation results indicate that RNNM, which has a per-iteration complexity of a semidefinite program, is effective in designing aligned beamformers for proper-feasible systems with or without redundant antennas, while RFNM and AM, which have a per-iteration complexity of a quadratic program, are better suited for systems with redundant antennas.

This paper is concerned with Gaussian approximations to the posterior probability density function (PDF) in the update step of Bayesian filtering with nonlinear measurements. In this setting, sigma-point approximations to the Kalman filter (KF) recursion are widely used due to their ease of implementation and relatively good performance. In the update step, these sigma-point KFs are equivalent to linearizing the nonlinear measurement function by statistical linear regression (SLR) with respect to the prior PDF. In this paper, we argue that the measurement function should be linearized using SLR with respect to the posterior rather than the prior to take into account the information provided by the measurement. The resulting filter is referred to as the posterior linearization filter (PLF). In practice, the exact PLF update is intractable but can be approximated by the iterated PLF (IPLF), which carries out iterated SLRs with respect to the best available approximation to the posterior. The IPLF can be seen as an approximate recursive Kullback-Leibler divergence minimization procedure. We demonstrate the high performance of the IPLF in relation to other Gaussian filters in two numerical examples.

Bayesian tracking is a general technique for state estimation of nonlinear dynamic systems, but it suffers from the drawback of computational complexity. This paper is concerned with a class of Wiener systems with multiple nonlinear sensors. Such a system consists of a linear dynamic system followed by a set of static nonlinear measurements. We study a maximum-likelihood Kalman filtering (MLKF) technique which involves maximum-likelihood estimation of the nonlinear measurements followed by classical Kalman filtering. This technique permits a distributed implementation of the Bayesian tracker and guarantees the boundedness of the estimation error. The focus of this paper is to study the extent to which the MLKF technique approximates the theoretically optimal Bayesian tracker. We provide conditions to guarantee that this approximation becomes asymptotically exact as the number of sensors becomes large. Two case studies are analyzed in detail.

Zero-forcing beamforming under per-antenna power constraint (PAPC) is considered in this paper, and the objective is to maximize the minimum user information rate. A parallel low complexity zero-forcing beamformer design is proposed in this paper for MU-MIMO systems by introducing a regularized dual decomposition method. The idea of this method is to solve the problem via solving its dual problem. Since the dual objective is not differentiable, a Tikhonov regularization is introduced. The regularized problem can be solved by using a gradient-based method in a parallel manner. Moreover, the optimal solution of the Lagrangian is in a closed form. The smoothness properties of the regularized dual function are investigated. We also estimate the error bound between the optimal function value of the primal problem and that of the regularized dual problem. Corresponding convergence analysis and convergence rate of the proposed algorithm are established. Computational complexity analysis is carried out to compare the complexity of the proposed method with that of state-of-the-art interior point method. Simulation results are provided to show the effectiveness of the proposed method.

We consider the problem of approximating optimal in the Minimum Mean Squared Error (MMSE) sense nonlinear filters in a discrete time setting, exploiting properties of stochastically convergent state process approximations. More specifically, we consider a class of nonlinear, partially observable stochastic systems, comprised by a (possibly nonstationary) hidden stochastic process (the state), observed through another conditionally Gaussian stochastic process (the observations). Under general assumptions, we show that, given an approximating process which, for each time step, is stochastically convergent to the state process, an approximate filtering operator can be defined, which converges to the true optimal nonlinear filter of the state in a strong and well defined sense. In particular, the convergence is compact in time and uniform in a completely characterized measurable set of probability measure almost unity, also providing a purely quantitative justification of Egoroff's Theorem for the problem at hand. The results presented in this paper can form a common basis for the analysis and characterization of a number of heuristic approaches for approximating optimal nonlinear filters, such as approximate grid based techniques, known to perform well in a variety of applications., EXTENDED version of an original paper published in the IEEE Transactions on Signal Processing; 37 pages

In this paper, cooperative sensor localization using asynchronous time-of-arrival measurements is investigated. It is well known that localization performance in wireless networks using time-based ranging or pseudo-ranging methods is greatly affected by the accuracy of the timing synchronization between the nodes involved in the estimation. Commonly, the original estimation problem is broken down into two subproblems, the synchronization problem and the localization problem, in what is known as a two-step approach. However, in this paper, the joint synchronization and localization problem is considered and examined for use in cooperative networks. It is discussed that the cooperation between the source nodes eliminates the need for high anchor node densities and improves localization performance significantly. Furthermore, the Cramer-Rao lower bounds (CRLB) and the maximum likelihood (ML) estimator are derived. It is shown that the ML estimator is highly nonlinear and nonconvex and must, therefore, be solved by using computationally complex algorithms. In order to reduce the complexity of the estimation, a novel semidefinite programming (SDP) relaxation method is developed by relaxing the original nonconvex ML problem, in such a way as to reformulate the estimation problem as a convex problem. The performance of the proposed SDP method is shown through computer simulations to nearly equal that of the ML estimator. The approach is also applied to the noncooperative case where it is found to be superior in performance than the previously proposed suboptimal estimators. Finally, complexity analyses are included for the estimators under consideration.

This paper studies the coordinated beamforming (CoBF) design for the multiple-input single-output interference channel, provided that only channel distribution information is known to the transmitters. The problem under consideration is a probabilistically constrained optimization problem which maximizes a predefined system utility subject to constraints on rate outage probability and power budget of each transmitter. Our recent analysis has shown that the outage-constrained CoBF problem is intricately difficult, e.g., NP-hard. Therefore, the focus of this paper is on suboptimal but computationally efficient algorithms. Specifically, by leveraging on the block successive upper bound minimization (BSUM) method in optimization, we propose a Gauss-Seidel type algorithm, called distributed BSUM algorithm, which can handle differentiable, monotone and concave system utilities. By exploiting a weighted minimum mean-square error (WMMSE) reformulation, we further propose a Jocobi-type algorithm, called distributed WMMSE algorithm, which can optimize the weighted sum rate utility in a fully parallel manner. To provide a performance benchmark, a relaxed approximation method based on polyblock outer approximation is also proposed. Simulation results show that the proposed algorithms are significantly superior to the existing successive convex approximation method in both performance and computational efficiency, and can yield promising approximation performance., submitted to IEEE Transactions on Signal Processing

International audience; This paper addresses the problem of the Clutter Subspace Projector (CSP) estimation in the context of a disturbance composed of a Low Rank (LR) heterogeneous clutter , modeled here by a Spherically Invariant Random Vector (SIRV), plus a white Gaussian noise (WGN). In such context, the corresponding LR adaptive filters and detectors require less training vectors than classical methods to reach equivalent performance. Unlike classical adaptive processes, which are based on an estimate of the noise Covariance Matrix (CM), the LR processes are based on a CSP estimate. This CSP estimate is usually derived from a Singular Value Decomposition (SVD) of the CM estimate. However, no Maximum Likelihood Estimator (MLE) of the CM has been derived for the considered disturbance model. In this paper, we introduce the fixed point equation that MLE of the CSP satisfies for a disturbance composed of a LR-SIRV clutter plus a zero mean WGN. A recursive algorithm is proposed to compute this solution. Numerical simulations validate the introduced estimator and illustrate its interest compared to the current state of art.

This paper studies a sensor selection problem. A group of sensors measure the state of a process and send their measurements to a remote estimator. Due to communication constraints, only limited sensors are allowed to communicate with the estimator. The paper intends to answer which sensors should be chosen such that the estimation performance of the estimator is optimized. Both reliable and packet-dropping channels are considered. It is required to minimize the steady-state estimation error covariance for reliable channels and to minimize the upper bound of the expected estimation error covariance for packet-dropping channels. For both scenarios, the original optimization problems are transformed to problems which can be solved by convex optimization techniques.

An analytic solution to the multi-target Bayes recursion known as the $\delta $ -Generalized Labeled Multi-Bernoulli ( $\delta $ -GLMB) filter has been recently proposed by Vo and Vo in [“Labeled Random Finite Sets and Multi-Object Conjugate Priors,” IEEE Trans. Signal Process., vol. 61, no. 13, pp. 3460–3475, 2014]. As a sequel to that paper, the present paper details efficient implementations of the $\delta $ -GLMB multi-target tracking filter. Each iteration of this filter involves an update operation and a prediction operation, both of which result in weighted sums of multi-target exponentials with intractably large number of terms. To truncate these sums, the ranked assignment and K-th shortest path algorithms are used in the update and prediction, respectively, to determine the most significant terms without exhaustively computing all of the terms. In addition, using tools derived from the same framework, such as probability hypothesis density filtering, we present inexpensive (relative to the $\delta $ -GLMB filter) look-ahead strategies to reduce the number of computations. Characterization of the $L_{1}$ -error in the multi-target density arising from the truncation is presented.

Interest in parameterized time-frequency analysis for non-stationary signal processing is increasing steadily. An important advantage of such analysis is to provide highly concentrated time-frequency representation with signal-dependent resolution. In this paper, a general scheme, named as general parameterized time-frequency transform (GPTF transform), is proposed for carrying out parameterized time-frequency analysis. The GPTF transform is defined by applying generalized kernel based rotation operator and shift operator. It provides the availability of a single generalized time-frequency transform for applications on signals of different natures. Furthermore, by replacing kernel function, it facilitates the implementation of various parameterized time – frequency transforms from the same standpoint. The desirable properties and the dual definition in the frequency domain of GPTF transform are also described in this paper. One of the advantages of the GPTF transform is that the generalized kernel can be customized to characterize the time – frequency signature of non-stationary signal. As different kernel formulation has bias toward the signal to be analyzed, a proper kernel is vital to the GPTF. Thus, several potential kernels are provided and discussed in this paper to develop the desired parameterized time – frequency transforms. In real applications, it is desired to identify proper kernel with respect to the considered signal. This motivates us to propose an effective method to identify the kernel for the GPTF.

We propose a novel decomposition framework for the distributed optimization of Difference Convex (DC)-type nonseparable sum-utility functions subject to coupling convex constraints. A major contribution of the paper is to develop for the first time a class of (inexact) best-response-like algorithms with provable convergence, where a suitably convexified version of the original DC program is iteratively solved. The main feature of the proposed successive convex approximation method is its decomposability structure across the users, which leads naturally to distributed algorithms in the primal and/or dual domain. The proposed framework is applicable to a variety of multiuser DC problems in different areas, ranging from signal processing, to communications and networking. As a case study, in the second part of the paper we focus on two examples, namely: i) a novel resource allocation problem in the emerging area of cooperative physical layer security and ii) and the renowned sum-rate maximization of MIMO Cognitive Radio networks. Our contribution in this context is to devise a class of easy-to-implement distributed algorithms with provable convergence to stationary solution of such problems. Numerical results show that the proposed distributed schemes reach performance close to (and sometimes better than) that of centralized methods.

This paper seeks to combine linear time-invariant (LTI) filtering and sparsity-based denoising in a principled way in order to effectively filter (denoise) a wider class of signals. LTI filtering is most suitable for signals restricted to a known frequency band, while sparsity-based denoising is suitable for signals admitting a sparse representation with respect to a known transform. However, some signals cannot be accurately categorized as either band-limited or sparse. This paper addresses the problem of filtering noisy data for the particular case where the underlying signal comprises a low-frequency component and a sparse or sparse-derivative component. A convex optimization approach is presented and two algorithms derived: one based on majorization-minimization (MM), and the other based on the alternating direction method of multipliers (ADMM). It is shown that a particular choice of discrete-time filter, namely zero-phase noncausal recursive filters for finite-length data formulated in terms of banded matrices, makes the algorithms effective and computationally efficient. The efficiency stems from the use of fast algorithms for solving banded systems of linear equations. The method is illustrated using data from a physiological-measurement technique (i.e., near infrared spectroscopic time series imaging) that in many cases yields data that is well-approximated as the sum of low-frequency, sparse or sparse-derivative, and noise components.

Stochastic orders are binary relations defined on probability distributions which capture intuitive notions like being larger or being more variable. This paper introduces stochastic ordering of interference distributions in large-scale networks modeled as point processes. Interference is a major performance-limiting factor in most wireless networks, thus it is important to characterize its statistics. Since closed-form results for the distribution of interference for such networks are only available in limited cases, it is of interest to compare network interference using stochastic orders, for two different point processes with different fading or path-loss scenarios between the interferers and the receiver. In this paper, conditions on the fading distribution and path-loss model are given to establish stochastic ordering between interferences. Moreover, Laplace functional ordering is defined between point processes and applied for comparing interference. Monte-Carlo simulations are used to supplement our analytical results. The useful applications of this research are also provided.

In this paper, we extend the generalized approximate message passing (G-AMP) approach, originally proposed for high-dimensional generalized-linear regression in the context of compressive sensing, to the generalized-bilinear case. In Part I of this two-part paper, we derived our Bilinear G-AMP (BiG-AMP) algorithm as an approximation of the sum-product belief propagation algorithm in the high-dimensional limit, and proposed an adaptive damping mechanism that aids convergence under finite problem sizes, an expectation-maximization (EM)-based method to automatically tune the parameters of the assumed priors, and two rank-selection strategies. Here, in Part II, we discuss the specializations of BiG-AMP to the problems of matrix completion, robust PCA, and dictionary learning, and present the results of an extensive empirical study comparing BiG-AMP to state-of-the-art algorithms on each problem. Our numerical results, using both synthetic and real-world datasets, demonstrate that EM-BiG-AMP yields excellent reconstruction accuracy (often best in class) while maintaining competitive runtimes.

In this paper, we consider the problem of sparse error correction from general nonlinear measurements, which has applications in state estimation of electrical power networks, when bad data (outliers) are present. An iterative mixed l1 and l2 convex program is used to estimate the true state by locally linearizing the nonlinear measurements. In the special case when the measurements are linear, through using the almost Euclidean property for a linear subspace, we derive a new performance bound for the state estimation error under sparse bad data and additive observation noise. As a byproduct, in this paper we provide sharp bounds on the almost Euclidean property of a linear subspace, using the “escape-through-the-mesh” theorem from geometric functional analysis. When the measurements are nonlinear, we give conditions under which the solution of the iterative algorithm converges to the true state even though the locally linearized measurements may not be the actual nonlinear measurements. We are able to use a semidefinite program to verify the conditions for convergence of the proposed iterative sparse recovery algorithms from nonlinear measurements. We then numerically evaluate our iterative convex programming approach of performing bad data detections in nonlinear electrical power networks problems.

The Probability Hypothesis Density Filter (PHD) is a multitarget tracker for recursively estimating the number of targets and their state vectors from a set of observations. The PHD filter is capable of working well in scenarios with false alarms and missed detections. Two distinct PHD filter implementations are available in the literature: the Sequential Monte Carlo Probability Hypothesis Density (SMC-PHD) and the Gaussian Mixture Probability Hypothesis Density (GM-PHD) filters. The SMC-PHD filter uses particles to provide target state estimates, which can lead to a high computational load, whereas the GM-PHD filter does not use particles, but restricts to linear Gaussian mixture models. The SMC-PHD filter technique provides only weighted samples at discrete points in the state space instead of a continuous estimate of the probability density function of the system state and thus suffers from the well-known degeneracy problem. This paper proposes a B-Spline based Probability Hypothesis Density (S-PHD) filter, which has the capability to model any arbitrary probability density function. The resulting algorithm can handle linear, non-linear, Gaussian, and non-Gaussian models and the S-PHD filter can also provide continuous estimates of the probability density function of the system state. In addition, by moving the knots dynamically, the S-PHD filter ensures that the splines cover only the region where the probability of the system state is significant, hence the high efficiency of the S-PHD filter is maintained at all times. Also, unlike the SMC-PHD filter, the S-PHD filter is immune to the degeneracy problem due to its continuous nature. The S-PHD filter derivations and simulations are provided in this paper.

Given a limited number of entries from the superposition of a low-rank matrix plus the product of a known compression matrix times a sparse matrix, recovery of the low-rank and sparse components is a fundamental task subsuming compressed sensing, matrix completion, and principal components pursuit. This paper develops algorithms for decentralized sparsity-regularized rank minimization over networks, when the nuclear- and l1-norm are used as surrogates to the rank and nonzero entry counts of the sought matrices, respectively. While nuclear-norm minimization has well-documented merits when centralized processing is viable, non-separability of the singular-value sum challenges its decentralized minimization. To overcome this limitation, leveraging an alternative characterization of the nuclear norm yields a separable, yet non-convex cost minimized via the alternating-direction method of multipliers. Interestingly, if the decentralized (non-convex) estimator converges, under certain conditions it provably attains the global optimum of its centralized counterpart. As a result, this paper bridges the performance gap between centralized and in-network decentralized, sparsity-regularized rank minimization. This, in turn, facilitates (stable) recovery of the low rank and sparse model matrices through reduced-complexity per-node computations, and affordable message passing among single-hop neighbors. Several application domains are outlined to highlight the generality and impact of the proposed framework. These include unveiling traffic anomalies in backbone networks, and predicting networkwide path latencies. Simulations with synthetic and real network data confirm the convergence of the novel decentralized algorithm, and its centralized performance guarantees.

In this paper, we consider cognitive beamforming for multiple secondary data streams subject to individual signal-to-noise ratio (SNR) requirements for each secondary data stream. In such a cognitive radio system, the secondary user is permitted to use the spectrum allocated to the primary user as long as the caused interference at the primary receiver is tolerable. With both secondary SNR constraint and primary interference power constraint, we aim to minimize the secondary transmit power consumption. By exploiting the individual SNR requirements, we formulate this cognitive beamforming problem as an optimization problem on the Stiefel manifold. Both zero forcing beamforming (ZFB) and nonzero forcing beamforming (NFB) are considered. For the ZFB case, we derive a closed form beamforming solution. For the NFB case, we prove that the strong duality holds for the nonconvex primal problem and thus the optimal solution can be easily obtained by solving the dual problem. Finally, numerical results are presented to illustrate the performance of the proposed cognitive beamforming solutions., Comment: This is the longer version of a paper to appear in the IEEE Transactions on Signal Processing

In this paper, we consider the delay-constrained beamforming control for downlink multi-user MIMO (MU- MIMO) systems with imperfect channel state information at the transmitter (CSIT). The delay-constrained control problem is formulated as an infinite horizon average cost partially observed Markov decision process. To deal with the curse of dimensionality, we introduce a virtual continuous time system and derive a closed-form approximate value function using perturbation analysis w.r.t. the CSIT errors. To deal with the challenge of the conditional packet error rate (PER), we build a tractable closed- form approximation using a Bernstein-type inequality. Based on the closed-form approximations of the relative value function and the conditional PER, we propose a conservative formulation of the original beamforming control problem. The conservative problem is non-convex and we transform it into a convex problem using the semidefinite relaxation (SDR) technique. We then propose an alternating iterative algorithm to solve the SDR problem. Finally, the proposed scheme is compared with various baselines through simulations and it is shown that significant performance gain can be achieved., Comment: 14 pages, 7 figures, 1 table. This paper has been accepted by the IEEE Transactions on Signal Processing

This paper studies a sparse signal recovery task in time-varying (time-adaptive) environments. The contribution of the paper to sparsity-aware online learning is threefold; first, a Generalized Thresholding (GT) operator, which relates to both convex and non-convex penalty functions, is introduced. This operator embodies, in a unified way, the majority of well-known thresholding rules which promote sparsity. Second, a non-convexly constrained, sparsity-promoting, online learning scheme, namely the Adaptive Projection-based Generalized Thresholding (APGT), is developed that incorporates the GT operator with a computational complexity that scales linearly to the number of unknowns. Third, the novel family of partially quasi-nonexpansive mappings is introduced as a functional analytic tool for treating the GT operator. By building upon the rich fixed point theory, the previous class of mappings helps us, also, to establish a link between the GT operator and a union of linear subspaces; a non-convex object which lies at the heart of any sparsity promoting technique, batch or online. Based on such a functional analytic framework, a convergence analysis of the APGT is provided. Furthermore, extensive experiments suggest that the APGT exhibits competitive performance when compared to computationally more demanding alternatives, such as the sparsity-promoting Affine Projection Algorithm (APA)- and Recursive Least Squares (RLS)-based techniques.

Randomized (dithered) quantization is a method capable of achieving white reconstruction error independent of the source. Dithered quantizers have traditionally been considered within their natural setting of uniform quantization. In this paper we extend conventional dithered quantization to nonuniform quantization, via a subterfage: dithering is performed in the companded domain. Closed form necessary conditions for optimality of the compressor and expander mappings are derived for both fixed and variable rate randomized quantization. Numerically, mappings are optimized by iteratively imposing these necessary conditions. The framework is extended to include an explicit constraint that deterministic or randomized quantizers yield reconstruction error that is uncorrelated with the source. Surprising theoretical results show direct and simple connection between the optimal constrained quantizers and their unconstrained counterparts. Numerical results for the Gaussian source provide strong evidence that the proposed constrained randomized quantizer outperforms the conventional dithered quantizer, as well as the constrained deterministic quantizer. Moreover, the proposed constrained quantizer renders the reconstruction error nearly white. In the second part of the paper, we investigate whether uncorrelated reconstruction error requires random coding to achieve asymptotic optimality. We show that for a Gaussian source, the optimal vector quantizer of asymptotically high dimension whose quantization error is uncorrelated with the source, is indeed random. Thus, random encoding in this setting of rate-distortion theory, is not merely a tool to characterize performance bounds, but a required property of quantizers that approach such bounds., Comment: submitted to IEEE Transactions on Signal Processing, 2012

Unique-word (UW) OFDM is a new multicarrier technique that was recently proposed in [M. Huemer, C. Hofbauer, and J. B. Huber, “The Potential of Unique Words in OFDM, Proc. InOWo, Hamburg, Germany, Sep. 2010, pp. 140-144]. In this technique, the guard interval that contains a priori known samples is part of the FFT interval. To be able to construct the UW-OFDM signal, some carriers must be sacrificed to transmit redundant information-these carriers are called the redundant carriers. It turns out that the average redundant energy needed strongly depends on the positions of the redundant carriers. In this paper, we look for the redundant carrier placement that minimizes the average redundant energy. However, this optimization is a NP-hard problem. Therefore, we reformulate the optimization problem and implement a branch and bound (B&B) algorithm to find the optimum. The results of the B&B search algorithm are compared to a theoretical lower bound, and with the results for two low cost redundant carrier placements, i.e., the quasi-uniform (QU) distribution [H. Steendam, “The Quasi-Uniform Redundant Carrier Placement for UW-OFDM,” Vehicular Technology Conf., Fall 2012, Quebec, Canada, Sep. 2012], for the case where no guard bands are present, and the maximum distance (MD) distribution, in case forbidden guard bands are present. We show in this paper that when the full band is available for redundant carriers, both the redundant carrier placement found with the B&B algorithm and the QU distribution result in a redundant energy that is very close to the theoretical lower bound. Although the B&B slightly outperforms the QU distribution, this implies that the QU distribution is a good low cost solution to the redundant carrier placement problem in the case of no guard bands. However, when there are forbidden guard bands in which the redundant carriers cannot be placed, the QU distribution can no longer be used. In that case, the results of the B&B algorithm are compared to that of the MD distribution. We show in this paper that the proposed B&B algorithm outperforms the MD distribution in the sense that it needs noticeably lower redundant energy.

This paper studies the coordinated beamforming design problem for the multiple-input single-output (MISO) interference channel, assuming only channel distribution information (CDI) at the transmitters. Under a given requirement on the rate outage probability for receivers, we aim to maximize the system utility (e.g., the weighted sum rate, weighted geometric mean rate, and the weighed harmonic mean rate) subject to the rate outage constraints and individual power constraints. The outage constraints, however, lead to a complicated, nonconvex structure for the considered beamforming design problem and make the optimization problem difficult to handle. {Although} this nonconvex optimization problem can be solved in an exhaustive search manner, this brute-force approach is only feasible when the number of transmitter-receiver pairs is small. For a system with a large number of transmitter-receiver pairs, computationally efficient alternatives are necessary. The focus of this paper is hence on the design of such efficient approximation methods. In particular, by employing semidefinite relaxation (SDR) and first-order approximation techniques, we propose an efficient successive convex approximation (SCA) algorithm that provides high-quality approximate beamforming solutions via solving a sequence of convex approximation problems. The solution thus obtained is further shown to be a stationary point for the SDR of the original outage constrained beamforming design problem. {Furthermore}, we propose a distributed SCA algorithm where each transmitter optimizes its own beamformer using local CDI and information obtained from limited message exchange with the other transmitters. Our simulation results demonstrate that the proposed SCA algorithm and its distributed counterpart indeed converge, and near-optimal performance can be achieved for all the considered system utilities., 30 pages, 10 figures, accepted by IEEE Trans. Signal Process