Search

We consider stochastic optimization of a smooth non-convex loss function with a convex non-smooth regularizer. In the online setting, where a single sample of the stochastic gradient of the loss is available at every iteration, the problem can be solved using the proximal stochastic gradient descent (SGD) algorithm and its variants. However in many problems, especially those arising in communications and signal processing, information beyond the stochastic gradient may be available thanks to the structure of the loss function. By constructing a strongly convex surrogate of the loss function at every iteration, the stochastic SCA algorithms can exploit the structural properties of the loss function. In this work, we take a closer look at the stochastic SCA algorithm and develop its asynchronous variant which can be used for resource allocation in wireless networks. While the stochastic SCA algorithm is known to converge asymptotically, its iteration complexity has not been well-studied, and is the focus of the current work. The insights obtained from the non-asymptotic analysis allow us to develop a more practical asynchronous variant of the stochastic SCA algorithm which allows the use of surrogate calculated in earlier iterations. We characterize precise bound on the maximum delay the algorithm can tolerate, while still achieving the same convergence rate. We apply the algorithm to the problem of linear precoding in wireless sensor networks, where it can be implemented at low complexity but is shown to perform well in practice. [ABSTRACT FROM AUTHOR]

In this paper, we consider the policy evaluation problem in reinforcement learning with agents on a decentralized and directed network. In order to evaluate the quality of a fixed policy in this decentralized setting, one option is for agents to run decentralized temporal-difference (TD) collaboratively. To account for the practical scenarios where the state and action spaces are large and malicious attacks emerge, we focus on the decentralized TD learning with linear function approximation in the presence of malicious agents (often termed as Byzantine agents). We propose a trimmed mean-based Byzantine-resilient decentralized TD algorithm to perform policy evaluation in this setting. We establish the finite-time convergence rate, as well as the asymptotic learning error that depends on the number of Byzantine agents. Numerical experiments corroborate the robustness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel adaptive importance sampling (AIS) algorithm for probabilistic inference. The sampler learns a proposal distribution adaptation strategy by framing AIS as a reinforcement learning problem. Under this structure, the proposal distribution of the sampler is treated as an agent whose state is controlled using a parameterized policy. At each iteration of the algorithm, the agent earns a reward that is related to its contribution to the variance of the AIS estimator of the normalization constant of the target distribution. Policy gradient methods are employed to learn a locally optimal policy that maximizes the expected value of the sum of all rewards. Numerical simulations on two different examples demonstrate promising results for the future application of the proposed method to complex Bayesian models. [ABSTRACT FROM AUTHOR]

In this paper, we extend the bilinear generalized approximate message passing (BiG-AMP) approach, originally proposed for high-dimensional generalized bilinear regression, to the multi-layer case for the handling of cascaded problem such as matrix-factorization problem arising in relay communication among others. Assuming statistically independent matrix entries with known priors, the new algorithm called ML-BiGAMP could approximate the general sum-product loopy belief propagation (LBP) in the high-dimensional limit enjoying a substantial reduction in computational complexity. We demonstrate that, in large system limit, the asymptotic MSE performance of ML-BiGAMP could be fully characterized via a set of simple one-dimensional equations termed state evolution (SE). We establish that the asymptotic MSE predicted by ML-BiGAMP’ SE matches perfectly the exact MMSE predicted by the replica method, which is well-known to be Bayes-optimal but infeasible in practice. This consistency indicates that the ML-BiGAMP may still retain the same Bayes-optimal performance as the MMSE estimator in high-dimensional applications, although ML-BiGAMP's computational burden is far lower. As an illustrative example of the general ML-BiGAMP, we provide a detector design that could estimate the channel fading and the data symbols jointly with high precision for the two-hop amplify-and-forward relay communication systems. [ABSTRACT FROM AUTHOR]

The first moment and second central moments of the portfolio return, a.k.a. mean and variance, have been widely employed to assess the expected profit and risk of the portfolio. Investors pursue higher mean and lower variance when designing the portfolios. The two moments can well describe the distribution of the portfolio return when it follows the Gaussian distribution. However, the real world distribution of assets return is usually asymmetric and heavy-tailed, which is far from being a Gaussian distribution. The asymmetry and the heavy-tailedness are characterized by the third and fourth central moments, i.e., skewness and kurtosis, respectively. Higher skewness and lower kurtosis are preferred to reduce the probability of extreme losses. However, incorporating high-order moments in the portfolio design is very difficult due to their non-convexity and rapidly increasing computational cost with the dimension. In this paper, we propose a very efficient and convergence-provable algorithm framework based on the successive convex approximation (SCA) algorithm to solve high-order portfolios. The efficiency of the proposed algorithm framework is demonstrated by the numerical experiments. [ABSTRACT FROM AUTHOR]

The emergence of big data has caused a dramatic shift in the operating regime for optimization algorithms. The performance bottleneck, which used to be computations, is now often communications. Several gradient compression techniques have been proposed to reduce the communication load at the price of a loss in solution accuracy. Recently, it has been shown how compression errors can be compensated for in the optimization algorithm to improve the solution accuracy. Even though convergence guarantees for error-compensated algorithms have been established, there is very limited theoretical support for quantifying the observed improvements in solution accuracy. In this paper, we show that Hessian-aided error compensation, unlike other existing schemes, avoids accumulation of compression errors on quadratic problems. We also present strong convergence guarantees of Hessian-based error compensation for stochastic gradient descent. Our numerical experiments highlight the benefits of Hessian-based error compensation, and demonstrate that similar convergence improvements are attained when only a diagonal Hessian approximation is used. [ABSTRACT FROM AUTHOR]

Recently, several promising approximate message passing (AMP) based algorithms have been developed for bilinear recovery with model Y = ∑k=1K bk Ak C + W, where { bk } and C are jointly recovered with known Ak from the noisy measurements Y. The bilinear recovery problem has many applications such as dictionary learning, self-calibration, compressive sensing with matrix uncertainty, etc. In this work, we propose a new approximate Bayesian inference algorithm for bilinear recovery, where AMP with unitary transformation (UTAMP) is integrated with belief propagation (BP), variational inference (VI) and expectation propagation (EP) to achieve efficient approximate inference. It is shown that, compared to state-of-the-art bilinear recovery algorithms, the proposed algorithm is much more robust and faster, leading to remarkably better performance. [ABSTRACT FROM AUTHOR]

The affine rank minimization (ARM) problem arises in many real-world applications. The goal is to recover a low-rank matrix from a small amount of noisy affine measurements. The original problem is NP-hard, and so directly solving the problem is computationally prohibitive. Approximate low-complexity solutions for ARM have recently attracted much research interest. In this paper, we design an iterative algorithm for ARM based on message passing principles. The proposed algorithm is termed turbo-type ARM (TARM), as inspired by the recently developed turbo compressed sensing algorithm for sparse signal recovery. We show that, for right-orthogonally invariant linear (ROIL) operators, a scalar function called state evolution can be established to accurately predict the behaviour of the TARM algorithm. We also show that TARM converges faster than the counterpart algorithms when ROIL operators are used for low-rank matrix recovery. We further extend the TARM algorithm for matrix completion, where the measurement operator corresponds to a random selection matrix. Slight improvement of the matrix completion performance has been demonstrated for the TARM algorithm over the state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

This work addresses the robust principal component analysis (PCA) problem using generalized nonoconvex regularization for low-rank and sparsity promotion. While the popular nuclear and $\ell _1$ -norm penalties have a bias problem, nonconvex regularization can alleviate the bias problem and can be expected to achieve better performance. In this paper, a proximal block coordinate descent (BCD) algorithm is used to efficiently solve the nonconvex regularized robust PCA problem. It is globally convergent under weak conditions. Further, for a popular class of penalties having discontinuous threshoding functions, we establish the convergence to a restricted strictly local minimizer and, also, a local linear convergence rate for the proximal BCD algorithm. Moreover, convergence to a local minimizer has been derived for hard-thresholding. Our result is the first on nonconvex robust PCA with established convergence to strictly local minimizer with local linear convergence rate. Numerical experiments have been provided to demonstrate the performance of the new algorithm. [ABSTRACT FROM AUTHOR]

Sparse coding refers to the pursuit of the sparsest representation of a signal in a typically overcomplete dictionary. From a Bayesian perspective, sparse coding provides a maximum a posteriori estimate of the unknown vector under a sparse prior. In this paper, we suggest enhancing the performance of sparse coding algorithms by a deliberate and controlled contamination of the input with random noise, a phenomenon known as stochastic resonance. The proposed method adds controlled noise to the input and estimates a sparse representation from the perturbed signal. A set of such solutions is then obtained by projecting the original input signal onto the recovered set of supports. We present two variants of the described method, which differ in their final step. The first is a provably convergent approximation to the minimum mean square error (MMSE) estimator, relying on the generative model and applying a weighted average over the recovered solutions. The second is a relaxed variant of the former that simply applies an empirical mean. We show that both methods provide a computationally efficient approximation to the MMSE estimator, which is typically intractable to compute. We demonstrate our findings empirically and provide a theoretical analysis of our method under several different cases. [ABSTRACT FROM AUTHOR]

A recursive maximum-likelihood algorithm (RML) is proposed that can be used when both the observations and the hidden data have continuous values and are statistically dependent between different time samples. The algorithm recursively approximates the probability density functions of the observed and hidden data by analytically computing the integrals with respect to the state variables, where the parameters are updated using gradient steps. A full convergence proof is given, based on the ordinary differential equation approach, which shows that the algorithm converges to a local minimum of the Kullback–Leibler divergence between the true and the estimated parametric probability density functions—a result that is useful even for a miss-specified parametric model. Compared to other RML algorithms proposed in the literature, this contribution extends the state-space model and provides a theoretical analysis in a nontrivial statistical model that was not analyzed so far. We further extend the RML analysis to constrained parameter estimation problems. Two examples, including nonlinear state-space models, are given to highlight this contribution. [ABSTRACT FROM AUTHOR]

In CANDECOMP/PARAFAC tensor decomposition, degeneracy often occurs in some difficult scenarios, especially, when the rank exceeds the tensor dimension, or when the loading components are highly collinear in several or all modes, or when CPD does not have an optimal solution. In such cases, norms of some rank-1 tensors become significantly large and cancel each other. This makes algorithms getting stuck in local minima while running a huge number of iterations does not improve the decomposition. In this paper, we propose an error preservation correction method to deal with such problem. Our aim is to seek an alternative tensor, which preserves the approximation error, but norms of rank-1 tensor components of the new tensor are minimized. Alternating and all-at-once correction algorithms have been developed for the problem. In addition, we propose a novel CPD with a bound constraint on the norm of the rank-one tensors. The method can be useful for decomposing tensors that cannot be performed by traditional algorithms. Finally, we demonstrate an application of the proposed method in image denoising and decomposition of the weight tensors in convolutional neural networks. [ABSTRACT FROM AUTHOR]

In this paper, a computationally efficient algorithm for Bayesian joint change point detection (CPD) in multiple time series is presented. The data generation model includes a number of change configurations (CC), each affecting a unique subset of the time series, which introduces correlation between the positions of change points (CPs) in the monitored time series. The inference objective is to identify joint changes and the associated CC. The algorithm consists of two stages: First, a univariate CPD algorithm is applied separately to each of the involved time series. The outcomes of this step are maximum a posteriori (MAP) detected CPs and posterior distributions of CPs conditioned on the MAP CPs. These outcomes are used in combination to approximate the posterior for the CCs. In the second algorithm stage, dynamic programming is used to find the maxima of this approximate CC posterior. The algorithm is applied to synthetic data, and it is shown to be both significantly faster and more accurate compared to a previously proposed algorithm designed to solve similar problems. Also, the initial algorithm is extended with steps from the maximization–maximization algorithm, which allows the hyperparameters of the data generation model to be estimated jointly with the CCs, and we show that these estimates coincide with estimates obtained from a Markov chain Monte Carlo algorithm. [ABSTRACT FROM AUTHOR]

We propose an iterative channel estimation algorithm based on the least square estimation (LSE) and sparse message passing (SMP) algorithm for the millimeter wave (mmWave) MIMO systems. The channel coefficients of the mmWave MIMO are approximately modeled as a Bernoulli–Gaussian distribution and the channel matrix is sparse with only a few nonzero entries. By leveraging the advantage of sparseness, we propose an algorithm that iteratively detects the exact locations and values of nonzero entries of the sparse channel matrix. At each iteration, the locations are detected by the SMP, and values are estimated with the LSE. We also analyze the Cramér–Rao Lower Bound (CLRB), and show that the proposed algorithm is a minimum variance unbiased estimator under the assumption that we have the partial priori knowledge of the channel. Furthermore, we employ the Gaussian approximation for message densities under density evolution to simplify the analysis of the algorithm, which provides a simple method to predict the performance of the proposed algorithm. Numerical experiments show that the proposed algorithm has much better performance than the existing sparse estimators, especially when the channel is sparse. In addition, our proposed algorithm converges to the CRLB of the genie-aided estimation of sparse channels with only five turbo iterations. [ABSTRACT FROM AUTHOR]

In this paper, four iterative algorithms for learning analysis operators are presented. They are built upon the same optimization principle underlying both Analysis K-SVD and Analysis SimCO. The forward and sequential analysis operator learning (AOL) algorithms are based on projected gradient descent with optimally chosen step size. The implicit AOL algorithm is inspired by the implicit Euler scheme for solving ordinary differential equations and does not require to choose a step size. The fourth algorithm, singular value AOL, uses a similar strategy as Analysis K-SVD while avoiding its high computational cost. All algorithms are proven to decrease or preserve the target function in each step and a characterization of their stationary points is provided. Further they are tested on synthetic and image data, compared to Analysis SimCO and found to give better recovery rates and faster decay of the objective function, respectively. In a final denoising experiment the presented algorithms are again shown to perform similar to or better than the state-of-the-art algorithm ASimCO. [ABSTRACT FROM AUTHOR]

Vector perturbation (VP) precoding is a promising technique for multiuser communication systems operating in the downlink. In this work, we introduce a hybrid framework to improve the performance of lattice reduction (LR) aided precoding in VP. First, we perform a simple precoding using zero forcing (ZF) or successive interference cancellation (SIC) based on a reduced lattice basis. Since the signal space after LR-ZF or LR-SIC precoding can be shown to be bounded to a small range, then along with sufficient orthogonality of the lattice basis guaranteed by LR, they collectively pave the way for the subsequent application of an approximate message passing (AMP) algorithm, which further boosts the performance of any suboptimal precoder. Our work shows that the AMP algorithm can be beneficial for a lattice decoding problem whose data symbols lie in integers $\mathbb {Z}$ and entries of the lattice basis may not be i.i.d. Gaussian. Numerical results confirm that the low-complexity AMP algorithm can improve the symbol error rate performance of LR-aided precoding significantly. Finally, the hybrid scheme is also proven effective when solving the data detection problem of massive MIMO systems without using LR. [ABSTRACT FROM AUTHOR]

This paper considers the reconstruction of a discrete-valued random vector from possibly underdetermined linear measurements using sum-of-absolute-value (SOAV) optimization. The proposed algorithm, referred to as discreteness-aware approximate message passing (DAMP), is based on the idea of approximate message passing (AMP), which has been originally proposed for compressed sensing. The DAMP algorithm has low computational complexity and its performance in the large system limit can be predicted analytically via state evolution framework, where we provide a condition for the exact reconstruction with DAMP in the noise-free case. From the analysis, we also propose a method to determine the parameters of the SOAV optimization. Moreover, based on the state evolution, we provide Bayes optimal DAMP, which has the minimum mean-square-error at each iteration of the algorithm. Simulation results show that the DAMP algorithms can reconstruct the discrete-valued vector from underdetermined linear measurements and the empirical performance agrees with our theoretical results in large-scale systems. When the problem size is not large enough, the SOAV optimization with the proposed parameters can achieve better performance than the DAMP algorithms for high signal-to-noise ratio. [ABSTRACT FROM AUTHOR]

Source localization and spectral estimation are among the most fundamental problems in statistical and array signal processing. Methods that rely on the orthogonality of the signal and noise subspaces, such as Pisarenko's method, MUSIC, and root-MUSIC, are some of the most widely used algorithms to solve these problems. As a common feature, these methods require both a priori knowledge of the number of sources and an estimate of the noise subspace. Both requirements are complicating factors to the practical implementation of the algorithms and, when not satisfied exactly, can potentially lead to severe errors. In this paper, we propose a new localization criterion based on the algebraic structure of the noise subspace that is described for the first time to the best of our knowledge. Using this criterion and the relationship between the source localization problem and the problem of computing the greatest common divisor (GCD), or more practically approximate GCD, for polynomials, we propose two algorithms, which adaptively learn the number of sources and estimate their locations. Simulation results show a significant improvement over root-MUSIC in challenging scenarios such as closely located sources, both in terms of detection of the number of sources and their localization over a broad and practical range of signal-to-noise ratios. Furthermore, no performance sacrifice in simple scenarios is observed. [ABSTRACT FROM AUTHOR]

BigBand is a technique for wideband spectrum sensing (WSS) that can capture gigahertz of sparse spectrum in real time by using shifted multiple channels without sampling the signal at GS/s. In this paper, we focus on enforcing BigBand with the proposed improved algorithm, namely, AD-BigBand, for efficient and robust computation. AD-BigBand converts the nonlinear process (locating frequency and computing the spectrum value) of sparse WSS into two steps of solving linear equations. In particular, we define an r -degree frequency locator polynomial to rapidly locate nonzero frequencies. The computing complexity of the proposed method decreases from O(K{\log ^2}K ({{{n\log K} \over K}})^{\log K}) of shifted sampling based BigBand to O(K{\log ^2}K)$, where the $K$-sparse signals of bandwitdth $n$ are subsampled with arithmetic time-shifted sensing channels. We implement AD-BigBand on a commercial four-channel acquisition card. Experimental results show that AD-BigBand improves the WSS capabilities and exhibits higher processing speed and lower error spectrum construction rate than BigBand, especially in the case of relative low signal-to-noise ratio. [ABSTRACT FROM AUTHOR]

In this paper, we present an algorithm for the sparse signal recovery problem that incorporates damped Gaussian generalized approximate message passing (GGAMP) into expectation-maximization-based sparse Bayesian learning (SBL). In particular, GGAMP is used to implement the E-step in SBL in place of matrix inversion, leveraging the fact that GGAMP is guaranteed to converge with appropriate damping. The resulting GGAMP-SBL algorithm is much more robust to arbitrary measurement matrix A than the standard damped GAMP algorithm while being much lower complexity than the standard SBL algorithm. We then extend the approach from the single measurement vector case to the temporally correlated multiple measurement vector case, leading to the GGAMP-TSBL algorithm. We verify the robustness and computational advantages of the proposed algorithms through numerical experiments. [ABSTRACT FROM AUTHOR]

We propose a geometric assumption on nonnegative data matrices such that under this assumption, we are able to provide upper bounds (both deterministic and probabilistic) on the relative error of nonnegative matrix factorization (NMF). The algorithm we propose first uses the geometric assumption to obtain an exact clustering of the columns of the data matrix; subsequently, it employs several rank-one NMFs to obtain the final decomposition. When applied to data matrices generated from our statistical model, we observe that our proposed algorithm produces factor matrices with comparable relative errors vis-à-vis classical NMF algorithms but with much faster speeds. On face image and hyperspectral imaging datasets, we demonstrate that our algorithm provides an excellent initialization for applying other NMF algorithms at a low computational cost. Finally, we show on face and text datasets that the combinations of our algorithm and several classical NMF algorithms outperform other algorithms in terms of clustering performance. [ABSTRACT FROM PUBLISHER]

Stochastic approximation techniques play an important role in solving many problems encountered in machine learning or adaptive signal processing. In these contexts, the statistics of the data are often unknown a priori or their direct computation is too intensive, and they have thus to be estimated online from the observed signals. For batch optimization of an objective function being the sum of a data fidelity term and a penalization (e.g., a sparsity promoting function), Majorize-Minimize (MM) methods have recently attracted much interest since they are fast, highly flexible, and effective in ensuring convergence. The goal of this paper is to show how these methods can be successfully extended to the case when the data fidelity term corresponds to a least squares criterion and the cost function is replaced by a sequence of stochastic approximations of it. In this context, we propose an online version of an MM subspace algorithm and we study its convergence by using suitable probabilistic tools. Simulation results illustrate the good practical performance of the proposed algorithm associated with a memory gradient subspace, when applied to both nonadaptive and adaptive filter identification problems. [ABSTRACT FROM PUBLISHER]

Consider the single-group multicast beamforming problem, where multiple users receive the same data stream simultaneously from a single transmitter. The problem is NP-hard and all existing algorithms for the problem either find suboptimal approximate or local stationary solutions. In this paper, we propose an efficient branch-and-bound algorithm for the problem that is guaranteed to find its global solution. To the best of our knowledge, our proposed algorithm is the first tailored global algorithm for the single-group multicast beamforming problem. Simulation results show that our proposed algorithm is computationally efficient (albeit its theoretical worst-case iteration complexity is exponential with respect to the number of receivers) and it significantly outperforms a state-of-the-art general-purpose global optimization solver called Baron. Our proposed algorithm provides an important benchmark for performance evaluation of existing algorithms for the same problem. By using it as the benchmark, we show that two state-of-the-art algorithms, semidefinite relaxation algorithm and successive linear approximation algorithm, work well when the problem dimension (i.e., the number of antennas at the transmitter and the number of receivers) is small but their performance deteriorates quickly as the problem dimension increases. [ABSTRACT FROM PUBLISHER]

The low-rank matrix completion problem is fundamental to a number of tasks in data mining, machine learning, and signal processing. This paper considers the problem of adaptive matrix completion in time-varying scenarios. Given a sequence of incomplete and noise-corrupted matrices, the goal is to recover and track the underlying low rank matrices. Motivated from the classical least-mean square (LMS) algorithms for adaptive filtering, three LMS-like algorithms are proposed for estimating and tracking low-rank matrices. Performance of the proposed algorithms is provided in form of nonasymptotic bounds on the tracking mean-square error. Tracking performance of the algorithms is also studied via detailed simulations over real-world datasets. [ABSTRACT FROM PUBLISHER]

We introduce the decentralized Broyden–Fletcher–Goldfarb–Shanno (D-BFGS) method as a variation of the BFGS quasi-Newton method for solving decentralized optimization problems. Decentralized quasi-Newton methods are of interest in problems that are not well conditioned, making first-order decentralized methods ineffective, and in which second-order information is not readily available, making second-order decentralized methods impossible. D-BFGS is a fully distributed algorithm in which nodes approximate curvature information of themselves and their neighbors through the satisfaction of a secant condition. We additionally provide a formulation of the algorithm in asynchronous settings. Convergence of D-BFGS is established formally in both the synchronous and asynchronous settings and strong performance advantages relative to existing methods are shown numerically. [ABSTRACT FROM PUBLISHER]

Estimating means of data points lying on the Riemannian manifold of symmetric positive-definite (SPD) matrices has proved of great utility in applications requiring interpolation, extrapolation, smoothing, signal detection, and classification. The power means of SPD matrices with exponent p in the interval [–1, 1] interpolate in between the Harmonic mean (p = –1) and the Arithmetic mean (p = 1), while the Geometric (Cartan/Karcher) mean, which is the one currently employed in most applications, corresponds to their limit evaluated at 0. In this paper, we treat the problem of estimating power means along the continuum p ∊ (–1, 1) given noisy observed measurement. We provide a general fixed point algorithm (MPM) and we show that its convergence rate for p = ±0.5 deteriorates very little with the number and dimension of points given as input. Along the whole continuum, MPM is also robust with respect to the dispersion of the points on the manifold (noise), much more than the gradient descent algorithm usually employed to estimate the geometric mean. Thus, MPM is an efficient algorithm for the whole family of power means, including the geometric mean, which by MPM can be approximated with a desired precision by interpolating two solutions obtained with a small ±p value. We also present an approximated version of the MPM algorithm with very low computational complexity for the special case p = ±½. Finally, we show the appeal of power means through the classification of brain–computer interface event-related potentials data. [ABSTRACT FROM PUBLISHER]

In the context of change-point detection, addressed by Total Variation minimization strategies, an efficient on-the-fly algorithm has been designed leading to exact solutions for univariate data. In this contribution, an extension of such an on-the-fly strategy to multivariate data is investigated. The proposed algorithm relies on the local validation of the Karush-Kuhn-Tucker conditions on the dual problem. Showing that the non-local nature of the multivariate setting precludes to obtain an exact on-the-fly solution, we devise an on-the-fly algorithm delivering an approximate solution, whose quality is controlled by a practitioner-tunable parameter, acting as a trade-off between quality and computational cost. Performance assessment shows that high quality solutions are obtained on-the-fly while benefiting of computational costs several orders of magnitude lower than standard iterative procedures. The proposed algorithm thus provides practitioners with an efficient multivariate change-point detection on-the-fly procedure. [ABSTRACT FROM PUBLISHER]

Greedy pursuit, which includes matching pursuit (MP) and orthogonal matching pursuit (OMP), is an efficient approach for sparse approximation. However, conventional greedy pursuit algorithms designed for inner product space are not robust against outliers. In this paper, we devise a new definition of correlation in \ell p-space with p>0, called \ell p-correlation, and introduce the concept of orthogonality in \ell p-space. Based on the \ell p-correlation and \ell p-orthogonality, which are generalizations of the absolute inner product and orthogonality of inner product space, respectively, we develop three greedy pursuit algorithms, namely, \ell p-MP, \ell p-OMP, and weak \ell p-MP, for robust sparse approximation in the presence of outliers. The convergence of the three algorithms is proved. In particular, the \ell p-norm of the residual of each algorithm decays exponentially. It is revealed that the exponential decay factor in the worst case is related to the minimal \ell p-correlation of the residual and the dictionary. Numerical examples on sparse signal recovery and harmonic retrieval in impulsive noise demonstrate that the \ell p-greedy pursuit algorithms with 0< p< 2 are more outlier-resistant than their counterparts in inner product space. [ABSTRACT FROM PUBLISHER]

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. [ABSTRACT FROM PUBLISHER]

In Part I of the study of the tensor deflation for CANDECOMP/PARAFAC, we have shown that the rank-1 tensor deflation is applicable under some conditions. Part II of the study presents several initialization algorithms suitable for the algorithm proposed in Part I. In addition, Part II contains an algorithm for the case when one or more factor matrices in the estimated model is constrained to be orthogonal. Finally, Part II provides an error analysis of the tensor deflation algorithm, which shows that there is a marginal loss of accuracy of the deflation algorithm compared to the ordinary CP decomposition. [ABSTRACT FROM PUBLISHER]

In an interference limited network, joint power and admission control (JPAC) aims at supporting a maximum number of links at their specified signal-to-interference-plus-noise ratio (SINR) targets while using minimum total transmission power. Various convex approximation deflation approaches have been developed for the JPAC problem. In this paper, we propose an effective polynomial time non-convex approximation deflation approach for solving the problem. The approach is based on the non-convex \ell q~(0< q< 1) approximation of an equivalent sparse \ell 0 reformulation of the JPAC problem. We show that, for any instance of the JPAC problem, there exists a \bar q\in (0,1) such that it can be exactly solved by solving its \ell q approximation problem with any q\in (0, \bar q]. We also show that finding the global solution of the \ell q approximation problem is NP-hard. Then, we propose a potential reduction interior-point algorithm, which can return an \epsilon -KKT solution of the NP-hard \ell q approximation problem in polynomial time. The returned solution can be used to check the simultaneous supportability of all links in the network and to guide an iterative link removal procedure, resulting in the polynomial time non-convex approximation deflation approach for the JPAC problem. Numerical simulations show that the proposed approach outperforms the existing convex approximation approaches in terms of the number of supported links and the total transmission power, particularly exhibiting a quite good performance in selecting which subset of links to support. [ABSTRACT FROM PUBLISHER]

We study the problem of binary sequential hypothesis testing using multiple sensors with associated observation costs. An off-line randomized sensor selection strategy, in which a sensor is chosen at every time step with a given probability, is considered. The objective of this work is to find a sequential detection rule and a sensor selection probability vector such that the expected total observation cost is minimized subject to constraints on reliability and sensor usage. First, the sequential probability ratio test is shown to be the optimal sequential detection rule in this framework as well. Efficient algorithms for obtaining the optimal sensor selection probability vector are then derived. In particular, a special class of problems in which the algorithm has complexity that is linear in the number of sensors is identified. An upper bound for the average sensor usage to estimate the error incurred due to Wald’s approximations is also presented. This bound can be used to set a safety margin for guaranteed satisfaction of the constraints on the sensor usage. [ABSTRACT FROM PUBLISHER]

Bayesian filtering aims at estimating sequentially a hidden process from an observed one. In particular, sequential Monte Carlo (SMC) techniques propagate in time weighted trajectories which represent the posterior probability density function (pdf) of the hidden process given the available observations. On the other hand, conditional Monte Carlo (CMC) is a variance reduction technique which replaces the estimator of a moment of interest by its conditional expectation given another variable. In this paper, we show that up to some adaptations, one can make use of the time recursive nature of SMC algorithms in order to propose natural temporal CMC estimators of some point estimates of the hidden process, which outperform the associated crude Monte Carlo (MC) estimator whatever the number of samples. We next show that our Bayesian CMC estimators can be computed exactly, or approximated efficiently, in some hidden Markov chain (HMC) models; in some jump Markov state-space systems (JMSS); as well as in multitarget filtering. Finally our algorithms are validated via simulations. [ABSTRACT FROM PUBLISHER]

Sparse signal restoration is usually formulated as the minimization of a quadratic cost function \Vert \mbi y - \mbi A \mbi x \Vert2^{2} where \mbi A is a dictionary and \mbi x is an unknown sparse vector. It is well-known that imposing an \ell 0 constraint leads to an NP-hard minimization problem. The convex relaxation approach has received considerable attention, where the \ell 0-norm is replaced by the \ell 1-norm. Among the many effective \ell 1 solvers, the homotopy algorithm minimizes \Vert \mbi y - \mbi A \mbi x \Vert2^{2}+\lambda \Vert \mbi x \Vert 1 with respect to \mbi x for a continuum of \lambda ’s. It is inspired by the piecewise regularity of the \ell 1-regularization path, also referred to as the homotopy path. In this paper, we address the minimization problem \Vert \mbi y - \mbi A \mbi x \Vert2^{2}+\lambda \Vert \mbi x \Vert 0 for a continuum of \lambda ’s and propose two heuristic search algorithms for \ell 0-homotopy. Continuation Single Best Replacement is a forward–backward greedy strategy extending the Single Best Replacement algorithm, previously proposed for \ell 0-minimization at a given \lambda . The adaptive search of the \lambda -values is inspired by \ell 1-homotopy. \ell 0 Regularization Path Descent is a more complex algorithm exploiting the structural properties of the \ell 0-regularization path, which is piecewise constant with respect to \lambda . Both algorithms are empirically evaluated for difficult inverse problems involving ill-conditioned dictionaries. Finally, we show that they can be easily coupled with usual methods of model order selection. [ABSTRACT FROM PUBLISHER]

This paper deals with the problem of joint complex matrix diagonalization by considering both the Hermitian and transpose congruences. We address the general case where the searched diagonalizing matrix is a priori nonunitary. Based on the minimization of a quadratic criterion, we propose a flexible algorithm in the sense that it allows to directly consider a rectangular diagonalizing matrix and to take into consideration both the Hermitian and transpose congruences within the same framework. The proposed algorithm is a coordinate descent algorithm that is based on an approximate criterion leading to the analytical derivation of the minima arguments. Computer simulations are drawn to illustrate the usefulness and performances of the algorithm and a comparison to state-of-the-art algorithms is presented. Finally, an application to independent component analysis based on fourth-order statistics is also presented. [ABSTRACT FROM PUBLISHER]

This paper addresses the problems of relabeling and summarizing posterior distributions that typically arise, in a Bayesian framework, when dealing with signal decomposition problems with an unknown number of components. Such posterior distributions are defined over union of subspaces of differing dimensionality and can be sampled from using modern Monte Carlo techniques, for instance, the increasingly popular RJ-MCMC method. No generic approach is available, however, to summarize the resulting variable-dimensional samples and extract from them component-specific parameters. We propose a novel approach, named Variable-dimensional Approximate Posterior for Relabeling and Summarizing (VAPoRS), to this problem, which consists of approximating the posterior distribution of interest by a “simple”—but still variable-dimensional—parametric distribution. The distance between the two distributions is measured using the Kullback–Leibler divergence, and a Stochastic EM-type algorithm, driven by the RJ-MCMC sampler, is proposed to estimate the parameters. Two signal decomposition problems are considered to show the capability of VAPoRS both for relabeling and for summarizing variable dimensional posterior distributions: the classical problem of detecting and estimating sinusoids in white Gaussian noise on the one hand, and a particle counting problem motivated by the Pierre Auger project in astrophysics on the other hand. [ABSTRACT FROM PUBLISHER]

This paper introduces a new algorithm to approximate non-orthogonal joint diagonalization (NOJD) of a set of complex matrices. This algorithm is based on the Frobenius norm formulation of the joint diagonalization (JD) problem and takes advantage from combining Givens and Shear rotations to attempt the approximate JD. It represents a non-trivial generalization of the JDi (Joint Diagonalization) algorithm (Souloumiac 2009) to the complex case. The JDi is first slightly modified then generalized to the CJDi (i.e., Complex JDi) using complex to real matrix transformation. Several methods already exist in the literature. Consequently, we provide herein a brief overview of existing NOJD algorithms. Then we provide an extensive comparative study to illustrate the effectiveness and stability of the CJDi with respect to various system parameters and application contexts. [ABSTRACT FROM AUTHOR]

In this paper, the problem of matrix rank minimization under affine constraints is addressed. The state-of-the-art algorithms can recover matrices with a rank much less than what is sufficient for the uniqueness of the solution of this optimization problem. We propose an algorithm based on a smooth approximation of the rank function, which practically improves recovery limits on the rank of the solution. This approximation leads to a non-convex program; thus, to avoid getting trapped in local solutions, we use the following scheme. Initially, a rough approximation of the rank function subject to the affine constraints is optimized. As the algorithm proceeds, finer approximations of the rank are optimized and the solver is initialized with the solution of the previous approximation until reaching the desired accuracy. On the theoretical side, benefiting from the spherical section property, we will show that the sequence of the solutions of the approximating programs converges to the minimum rank solution. On the experimental side, it will be shown that the proposed algorithm, termed SRF standing for smoothed rank function, can recover matrices, which are unique solutions of the rank minimization problem and yet not recoverable by nuclear norm minimization. Furthermore, it will be demonstrated that, in completing partially observed matrices, the accuracy of SRF is considerably and consistently better than some famous algorithms when the number of revealed entries is close to the minimum number of parameters that uniquely represent a low-rank matrix. [ABSTRACT FROM PUBLISHER]

The development of high-resolution two-dimensional spectral estimation techniques is of notable interest in synthetic aperture radar (SAR) imaging. Typically, data-independent techniques are exploited to form the SAR images, although such approaches will suffer from limited resolution and high sidelobe levels. Recent work on data-adaptive approaches have shown that both the iterative adaptive approach (IAA) and the sparse learning via iterative minimization (SLIM) algorithm offer excellent performance with high-resolution and low side lobe levels for both complete and incomplete data sets. Regrettably, both algorithms are computationally intensive if applied directly to the phase history data to form the SAR images. To help alleviate this, efficient implementations have also been proposed. In this paper, we further this work, proposing yet further improved implementation strategies, including approaches using the segmented IAA approach and the approximative quasi-Newton technique. Furthermore, we introduce a combined IAA-MAP algorithm as well as a hybrid IAA- and SLIM-based estimation scheme for SAR imaging. The effectiveness of the SAR imaging algorithms and the computational complexities of their fast implementations are demonstrated using the simulated Slicy data set and the experimentally measured GOTCHA data set. [ABSTRACT FROM PUBLISHER]

Graphical models use graphs to compactly capture stochastic dependencies amongst a collection of random variables. Inference over graphical models corresponds to finding marginal probability distributions given joint probability distributions. In general, this is computationally intractable, which has led to a quest for finding efficient approximate inference algorithms. We propose a framework for generalized inference over graphical models that can be used as a wrapper for improving the estimates of approximate inference algorithms. Instead of applying an inference algorithm to the original graph, we apply the inference algorithm to a block-graph, defined as a graph in which the nodes are non-overlapping clusters of nodes from the original graph. This results in marginal estimates of a cluster of nodes, which we further marginalize to get the marginal estimates of each node. Our proposed block-graph construction algorithm is simple, efficient, and motivated by the observation that approximate inference is more accurate on graphs with longer cycles. We present extensive numerical simulations that illustrate our block-graph framework with a variety of inference algorithms (e.g., those in the libDAI software package). These simulations show the improvements provided by our framework. [ABSTRACT FROM PUBLISHER]

Mixed-scaling-rotation (MSR) coordinate rotation digital computer (CORDIC) is an attractive approach to synthesizing complex rotators. This paper presents the fixed-point error analysis and parameter selections of MSR-CORDIC with applications to the fast Fourier transform (FFT). First, the fixed-point mean squared error of the MSR-CORDIC is analyzed by considering both the angle approximation error and signal round-off error incurred in the finite precision arithmetic. The signal to quantization noise ratio (SQNR) of the output of the FFT synthesized using MSR-CORDIC is thereafter estimated. Based on these analyses, two different parameter selection algorithms of MSR-CORDIC are proposed for general and dedicated MSR-CORDIC structures. The proposed algorithms minimize the number of adders and word-length when the SQNR of the FFT output is constrained. Design examples show that the FFT designed by the proposed method exhibits a lower hardware complexity than existing methods. [ABSTRACT FROM PUBLISHER]

High-resolution spectral Doppler is an important and powerful noninvasive tool for estimation of velocities in blood vessels using medical ultrasound scanners. Such estimates are typically formed using an averaged periodogram technique, resulting in well-known limitations in the resulting spectral resolution. Recently, we have proposed techniques to instead form high-resolution data-adaptive estimates exploiting measurements along both depth and emission. The resulting estimates gives noticeably superior velocity estimates as compared to the standard technique, but suffers from a high computational complexity, making it interesting to formulate computationally efficient implementations of the estimators. In this work, by exploiting the rich structure of the iterative adaptive approach (IAA) based estimator, we examine how these estimates can be efficiently implemented in a time-recursive manner using both exact and approximate formulations of the method. The resulting algorithms are shown to reduce the necessary computational load with several orders of magnitude without noticeable loss of performance. [ABSTRACT FROM PUBLISHER]

We propose a novel algorithm for compressive imaging that exploits both the sparsity and persistence across scales found in the 2D wavelet transform coefficients of natural images. Like other recent works, we model wavelet structure using a hidden Markov tree (HMT) but, unlike other works, ours is based on loopy belief propagation (LBP). For LBP, we adopt a recently proposed “turbo” message passing schedule that alternates between exploitation of HMT structure and exploitation of compressive-measurement structure. For the latter, we leverage Donoho, Maleki, and Montanari's recently proposed approximate message passing (AMP) algorithm. Experiments with a large image database suggest that, relative to existing schemes, our turbo LBP approach yields state-of-the-art reconstruction performance with substantial reduction in complexity. [ABSTRACT FROM PUBLISHER]

Intercell interference is the major limitation to the performance of future cellular systems. Despite the joint detection and joint transmission techniques aiming at interference cancelation which suffer from the limited possible cooperation among the nodes, power allocation is a promising approach for optimizing the system performance. If the interference is treated as noise, the power allocation optimization problem aiming at maximizing the sum rate with a total power constraint is nonconvex and up to now an open problem. In the present paper, the solution is found by reformulating the nonconvex objective function of the sum rate as a difference of two concave functions. A globally optimum power allocation is found by applying a branch-and-bound algorithm to the new formulation. In principle, the algorithm partitions the feasible region recursively into subregions where for every subregion the objective function is upper and lower bounded. For each subregion, a linear program is applied for estimating the upper bound of the sum rate which is derived from a convex maximization formulation of the problem with piecewise linearly approximated constraints. The performance is investigated by system-level simulations. The results show that the proposed algorithm outperforms the known conventional suboptimum schemes. Furthermore, it is shown that the algorithm asymptotically converges to a globally optimum power allocation. [ABSTRACT FROM PUBLISHER]

A method for adaptively minimizing the lp norm relying on the convex combination of two recursive least p-norm (RLpN) filters is presented. The approach is of interest when the noise is not Gaussian, for instance in the presence of impulsive or alpha-stable (\alpha \-S) distributed noise. In these cases, the RLpN algorithm, aiming at recursively minimizing the lp norm, offers a more stable and robust solution than adaptive filtering schemes based on the minimization of the squared error. However, since the RLpN solution cannot be obtained in closed form for p\ne 2, it is necessary to introduce some approximations that critically affect the filter behavior. The main observed drawback is a poor convergence rate in nonstationary scenarios, especially in the presence of abrupt changes in the model. In this correspondence, we show how this problem can be overcome by relying on convex combinations of two RLpN filters with long and short memories. The proposed methods are empirically shown to outperform state-of-the-art methods for this problem, requiring just slightly higher computation than its close competitors. [ABSTRACT FROM PUBLISHER]

The linear canonical transform (LCT) has been shown to be a powerful analyzing tool in signal processing. Many results of this transform are already known, including bandlimited extrapolation. The existing algorithm for solving the problem of LCT bandlimited extrapolation is based on signal expansion into a series of generalized prolate spheroidal wave functions (GPSWFs). However, the requirement to compute and store the GPSWFs and the errors due to the series truncation render this algorithm ill-suitable for a practical implementation. In this correspondence, we first propose a new formulation of the Gerchberg–Papoulis (GP) algorithm for LCT bandlimited extrapolation. Then, we present a fast convergence algorithm for the new formulation. The classical GP algorithm related to Fourier bandlimited signals is noted as a special case. Moreover, the comparison between the proposed algorithm and the one based on GPSWFs expansion is provided, and the validity of the theoretical derivations is demonstrated via simulations. Several potential applications of the achieved theory are also presented. [ABSTRACT FROM PUBLISHER]

We note that the well-known Fast Rayleigh's quotient-based Adaptive Noise Subspace (FRANS), FRANS with Householder transformation (HFRANS), and fast data projection method (FDPM) algorithms all inherit from the data projection method (DPM) algorithm, but with different orthonormalization matrices. Starting from the DPM, we analyze the orthonormalization matrices of all these algorithms and develop a novel orthonormalization matrix for our algorithm. Based on this novel orthonormalization matrix, a fast and stable implementation of the DPM algorithm which has the merits of both the FRANS and FDPM approaches is investigated for principal and minor subspace tracking. The proposed algorithm can switch between the principal and minor subspace tracking with a simple sign change of its step size parameter. Moreover, it reaches the 3np lower bound of the dominant complexity and guarantees the orthonormality of the tracked subspace. The numerical stability of our algorithm is established theoretically and tested numerically. The strengths and weaknesses of the proposed algorithm to some existing subspace tracking algorithms are demonstrated using a de facto benchmark example. Simulation results are presented to demonstrate the effectiveness of the tracking algorithm advocated. [ABSTRACT FROM PUBLISHER]

The blind identification of single-input multiple-output (SIMO) systems is often performed by exploiting a cross-relation (CR) between channel pairs. It has been shown that this property allows an estimation of channel impulse responses up to a common gain factor if certain identifiability conditions are met. In this case, the estimated channels can be evaluated by a gain-compensated system distance known as normalized projection misalignment (NPM). Current algorithms for blind channel identification, however, suffer in the presence of insufficient channel diversity and observation noise. In this paper, we first demonstrate that in the absence of noise the CR identification error for channels with exact common zeros is given by a single-channel pole-zero transfer function. Next, we extend our analysis to the realistic case of near-common zeros and noise for which we show that the effective error can still be approximated by a common transfer function as long as the distance between the channel zeros remains below a signal-to-noise ratio-dependent threshold. A finite impulse response (FIR) modeling of the error then enables us to define a common-filter-error-compensated system distance, termed normalized filter-projection misalignment (NFPM), which establishes a natural extension to the NPM analysis. By finally considering realistic channels, which we blindly estimate with the adaptive multichannel least mean-square (MCLMS) algorithm, we demonstrate that the NFPM reliably reaches the noise floor, confirming that the effective error can be approximated by a common FIR filter. [ABSTRACT FROM PUBLISHER]

Compressed sensing aims at reconstructing sparse signals from significantly reduced number of samples, and a popular reconstruction approach is \ell1-norm minimization. In this correspondence, a method called orthonormal expansion is presented to reformulate the basis pursuit problem for noiseless compressed sensing. Two algorithms are proposed based on convex optimization: one exactly solves the problem and the other is a relaxed version of the first one. The latter can be considered as a modified iterative soft thresholding algorithm and is easy to implement. Numerical simulation shows that, in dealing with noise-free measurements of sparse signals, the relaxed version is accurate, fast and competitive to the recent state-of-the-art algorithms. Its practical application is demonstrated in a more general case where signals of interest are approximately sparse and measurements are contaminated with noise. [ABSTRACT FROM AUTHOR]

We develop a novel sampling theorem on the sphere and corresponding fast algorithms by associating the sphere with the torus through a periodic extension. The fundamental property of any sampling theorem is the number of samples required to represent a band-limited signal. To represent exactly a signal on the sphere band-limited at L, all sampling theorems on the sphere require \cal O(L^2) samples. However, our sampling theorem requires less than half the number of samples of other equiangular sampling theorems on the sphere and an asymptotically identical, but smaller, number of samples than the Gauss-Legendre sampling theorem. The complexity of our algorithms scale as \cal O(L^3), however, the continual use of fast Fourier transforms reduces the constant prefactor associated with the asymptotic scaling considerably, resulting in algorithms that are fast. Furthermore, we do not require any precomputation and our algorithms apply to both scalar and spin functions on the sphere without any change in computational complexity or computation time. We make our implementation of these algorithms available publicly and perform numerical experiments demonstrating their speed and accuracy up to very high band-limits. Finally, we highlight the advantages of our sampling theorem in the context of potential applications, notably in the field of compressive sampling. [ABSTRACT FROM AUTHOR]