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

A new dirty paper coding technique that is robust against the gain attack is presented. Such a robustness is obtained by adopting a set of (orthogonal) equienergetic codewords and a correlation-based decoder. Due to the simple structure of orthogonal codes, we developed a simple yet powerful technique to embed the hidden message within the host signal. The proposed technique is an optimal one, in that the embedding distortion is minimized for a given robustness level, where robustness is measured through the maximum pairwise error probability in the presence of an additive Gaussian attack of given strength. The performance of the dirty coding algorithm is further improved by replacing orthogonal with quasi- orthogonal codes, namely, Gold sequences, and by concatenating them with an outer turbo code. To this aim, the inner decoder is modified to produce a soft estimate of the embedded message. Performance analysis is carried out by means of extensive simulations proving the validity of the novel watermarking scheme. [ABSTRACT FROM AUTHOR]

This paper proposes a novel algorithm to determine the optimal orientation of sensing axes of redundant inertial sensors such as accelerometers and gyroscopes (gyros) for increasing the sensing accuracy. In this paper, we have proposed a novel iterative algorithm to find the optimal sensor configuration. The proposed algorithm utilizes the majorization-minimization (MM) algorithm and the duality principle to find the optimal configuration. Unlike the state-of-the-art approaches which are mainly geometrical in nature and restricted to sensors’ noise being uncorrelated, the proposed algorithm gives the exact orientations of the sensors and can easily deal with the cases of correlated noise. The proposed algorithm has been implemented and tested via numerical simulation in the MATLAB. The simulation results show that the algorithm converges to the optimal configurations and shows the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

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]

The problem of range estimation based on noisy measurements with phase ambiguity can be solved using signals across multiple frequencies by existing algorithms based on either the Chinese Remainder Theorem or lattice theory. The performances of these algorithms are constrained by the trade-off between SNR of measurements and required estimation accuracy. In this paper, we firstly propose an algorithm to find a set of wavelengths satisfying the conditions to apply the closed-form lattice algorithm from a given interval. Then we propose an enhanced lattice algorithm for range estimation based on existing lattice approaches. In the conventional lattice algorithm, the selection of an integer vector by the estimator often fails to be the ground truth because of noise. As a result, the true value can be a neighbouring lattice point of the estimated point where neighbours are defined in terms of a distance depending on the noise characteristics. In this paper, all neighbouring lattice points of the estimated point obtained by a conventional lattice algorithm are regarded as candidates for the new estimate. Then an efficient estimator is presented to choose one of those candidates to be the new estimate. The performance of the proposed algorithm, i.e. the successful probability of reconstruction, is derived mathematically. Additionally, a computation-reduced algorithm is presented to reduce the overhead of computation. The calculated probability and simulation results demonstrate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

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

The Unlimited Sensing Framework (USF) was recently introduced to overcome the sensor saturation bottleneck in conventional digital acquisition systems. At its core, the USF converts a continuous-time high-dynamic-range (HDR) signal into folded, low-dynamic-range, modulo samples and allows the recovery of the HDR signal via algorithmic unfolding. In hardware, however, implementing ideal modulo folding requires careful calibration, analog design and high precision. At the interface of theory and practice, this paper explores a computational sampling strategy that relaxes strict hardware requirements via a novel, mathematically guaranteed reconstruction. We start with a generalized model for USF with two new parameters modeling hysteresis and folding transients in addition to the modulo threshold. Hysteresis accounts for mismatches between the reset threshold and the amplitude displacement at the folding time and the folding transient is a continuous transition period in the implementation of a reset. Both these effects are motivated by our hardware experiments and also occur in previous, domain-specific applications. We show that hysteresis is beneficial for USF and leverage it to derive the first recovery guarantees in the context of our generalized USF model for a certain sampling rate regime. Additionally, we show how the sampling rate requirement can be greatly reduced via a direct generalization of the proposed recovery. Our theoretical work is corroborated by hardware experiments with a hysteresis enabled, modulo ADC testbed comprising off-the-shelf electronic components. Thus, by capitalizing on a collaboration between hardware and algorithms, our paper enables an end-to-end pipeline for HDR sampling allowing more flexible hardware implementations. [ABSTRACT FROM AUTHOR]

In this paper, we propose to extend the standard Convolutional Dictionary Learning problem to a tensor representation where the activations are constrained to be “low-rank” through a Canonical Polyadic decomposition. We show that this additional constraint increases the robustness of the CDL with respect to noise and improve the interpretability of the final results. In addition, we discuss in detail the advantages of this representation and introduce two algorithms, based on ADMM or FISTA, that efficiently solve this problem. We show that by exploiting the low rank property of activations, they achieve lower complexity than the main CDL algorithms. Finally, we evaluate our approach on a wide range of experiments, highlighting the modularity and the advantages of this tensorial low-rank formulation. [ABSTRACT FROM AUTHOR]

This paper proposes a low complexity n-dimensional (nD) FastICA algorithm and architecture by introducing the concept of coordinate rotation where n\geq 2. The proposed algorithm can merge the two key steps of conventional FastICA—preprocessing and update and is therefore capable of reducing the hardware complexity of the conventional FastICA significantly as demonstrated in this paper. Hardware implementation can further be simplified due to the recursive nature of the proposed algorithm where the same 2D hardware module can be used as the fundamental core to implement nD architecture. Together with the algorithm formulation, its functionality is also validated and hardware complexity is analyzed and compared with the conventional nD FastICA. [ABSTRACT FROM PUBLISHER]

This paper studies the convergence properties of the well-known message-passing algorithm for convex optimisation. Under the assumption of pairwise separability and scaled diagonal dominance, asymptotic convergence is established and a simple bound for the convergence rate is provided for message-passing. In comparison with previous results, our results do not require the given convex program to have known convex pairwise components and that our bound for the convergence rate is tighter and simpler. When specialised to quadratic optimisation, we generalise known results by providing a very simple bound for the convergence rate. [ABSTRACT FROM AUTHOR]

This paper proposes an efficient algorithm for robust sensor placement with the purpose of recovering a source signal from noisy measurements. To model uncertainty on the spatially-variant sensors gain and on the spatially correlated noise, we assume that both are realizations of Gaussian processes. Since the signal to noise ratio (SNR) is also uncertain in this context, to achieve a robust signal extraction, we propose a new placement criterion based on the maximization of the probability that the SNR exceeds a given threshold. This criterion can be easily evaluated using the Gaussian process assumption. Moreover, to reduce the computational complexity of the joint maximization of the criterion with respect to all sensor positions, we suggest a sequential maximization approach, where the sensor positions are chosen one at a time. Finally, we present numerical results showing the superior robustness of the proposed approach when compared to standard sensor placement criteria aimed at interpolating the spatial gain and to a recently proposed criterion aimed at maximizing the average SNR. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the $\ell _1$ norm of a linear map over the sphere, which arises in various machine learning applications such as orthogonal dictionary learning (ODL) and robust subspace recovery (RSR). The problem is numerically challenging due to its nonsmooth objective and nonconvex constraint, and its algorithmic aspects have not been well explored. In this paper, we show how the manifold structure of the sphere can be exploited to design fast algorithms with provable guarantees for tackling this problem. Specifically, our contribution is fourfold. First, we present a manifold proximal point algorithm (ManPPA) for the problem and show that it converges at a global sublinear rate. Furthermore, we show that ManPPA can achieve a local quadratic convergence rate when applied to sharp instances of the problem. Second, we develop a semismooth Newton-based inexact augmented Lagrangian method for computing the search direction in each iteration of ManPPA and show that it has an asymptotic superlinear convergence rate. Third, we propose a stochastic variant of ManPPA called StManPPA, which is well suited for large-scale computation, and establish its sublinear convergence rate. Both ManPPA and StManPPA have provably faster convergence rates than existing subgradient-type methods. Fourth, using ManPPA as a building block, we propose a new heuristic method for solving a matrix analog of the problem, in which the sphere is replaced by the Stiefel manifold. The results from our extensive numerical experiments on the ODL and RSR problems demonstrate the efficiency and efficacy of our proposed methods. [ABSTRACT FROM AUTHOR]

Due to the advantage of capacity-achieving, polar codes have been extended to the block fading channel whereas most constructions involve complex iterative-calculation. In this paper, we establish a systematic framework to analyze the error performance of polar codes in the case of block mapping and random mapping. For both the mappings, by introducing the new concept, named split polar spectrum, we derive the upper bound on the error probability of polarized channel which explicitly reveals the relationship between the diversity order $L$ and the block-wise weight distribution of the codeword. For the special case $L=2$ in the block mapping, we design the enumeration algorithm to calculate the exact split polar spectrum based on the general MacWilliams identities. For arbitrary diversity order in the random mapping, with the help of uniform interleaving, we derive the approximate split polar spectrum by combining the polar spectrum and the probability of fading pattern for a specific weight. Furthermore, we propose the design criteria to construct polar codes over the block fading channel. The full diversity criterion is the primary target to achieve the diversity gain and the product distance criterion requires to maximize the product of the block-wise Hamming distance whereby obtain the coding gain. Guided by these design criteria, the construction metrics, respectively named polarized diversity weight (PDW) and simplified PDW (SPDW) are proposed to designpolar codes in both mappings. Such simple metrics can construct polar codes with similar or better performance over those based on traditional methods in block fading channel. [ABSTRACT FROM AUTHOR]

The paper derives the stability bound of the initial mean-square deviation of an adaptive filtering algorithm based on minimizing the 2Lth moment of the estimation error, with L being an integer greater than 1. The analysis is done for a time-invariant plant with even input probability density function. Dependence of the stability bound on the algorithm step-size, type of the noise distribution, signal-to-noise ratio (SNR), and L is studied. It is shown that the stability bound is decreasing in the step-size. The stability bound decreases as the tail of the noise probability density function becomes lighter for the same steady-state misadjustment. This result is surprising since, for example, it is expected that the stability of the least mean 2Lth algorithm for binary noise distribution is better than that for uniform distribution. The stability bound is proportional to the reciprocal of the SNR, another surprising result. Finally, the stability bound is decreasing in L, which implies a limitation on the ability to improve the performance of the adaptive filter by increasing the order of the cost function. Theoretical results are supported by simulations. [ABSTRACT FROM AUTHOR]

This paper studies how to deploy sensors in the context of detection in adversarial environments. A fusion center is performing a binary hypothesis testing based on measurements from remotely deployed heterogeneous sensors. An attacker may compromise some of the deployed sensors, which send arbitrary measurements to the fusion center. The problems of interest are: to characterize the performance of the system under attack and, thus, develop a performance metric; and to deploy sensors within a cost budget, such that the proposed performance metric is maximized. In this paper, we first present a performance metric by formulating the detection in adversarial environments in a game theoretic way. A Nash equilibrium pair of the detection algorithm and attack strategy, with the deployed sensors given, is provided and the corresponding detection performance is adopted as the performance metric. We then show that the optimal sensor deployment can be determined approximately by solving a group of unbounded knapsack problems. We also show that the performance metric gap between the optimal sensor deployment and the optimal one with sensors being identical is within a fixed constant for any cost budget. The main results are illustrated by numerical examples. [ABSTRACT FROM AUTHOR]

Classification with a sparsity constraint on the solution plays a central role in many high dimensional signal processing applications. In some cases, the features can be grouped together, so that entire subsets of features can be selected or discarded. In many applications, however, this can be too restrictive. In this paper, we are interested in a less restrictive form of structured sparse feature selection: We assume that while features can be grouped according to some notion of similarity, not all features in a group need be selected for the task at hand. The Sparse Group Lasso (SGL) was proposed to solve problems of this form. The main contributions of this paper are a new procedure called Sparse Overlapping Group (SOG) lasso, an extension to the SGL to overlapping groups and theoretical sample complexity bounds for the same. We establish model selection error bounds that specializes to many other cases. We experimentally validate our proposed method on both real and toy datasets. [ABSTRACT FROM AUTHOR]

Greed is good. However, the tighter you squeeze, the less you have. In this paper, a less greedy algorithm for sparse signal reconstruction in compressive sensing, named orthogonal matching pursuit with thresholding is studied. Using the global 2-coherence, which provides a “bridge” between the well known mutual coherence and the restricted isometry constant, the performance of orthogonal matching pursuit with thresholding is analyzed and more general results for sparse signal reconstruction are obtained. It is also shown that given the same assumption on the coherence index and the restricted isometry constant as required for orthogonal matching pursuit, the thresholding variation gives exactly the same reconstruction performance with significantly less complexity. [ABSTRACT FROM PUBLISHER]

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]

Passive source localization is one of the issues in array signal processing fields. In some practical applications, the signals received by an array are the mixture of near-field and far-field sources, such as speaker localization using microphone arrays and guidance (homing) systems. To localize mixed near-field and far-field sources, this paper develops a two-stage MUSIC algorithm using cumulant. The key points of this paper are: i) in the first stage, this paper derives one special cumulant matrix, in which the virtual "steering vector" is the function of the common electric angle in both near-field and far-field signal models so that source direction-of-arrival (DOA) (near-field or far-field one) can be obtained from this electric angle using the conventional high-resolution MUSIC algorithm; ii) in the second stage, this paper derives another particular cumulant matrix, in which the virtual "steering matrix" has full column rank no matter whether the received signals are multiple near-field sources or multiple far-field ones or their mixture. What is more important, the virtual "steering vector" can be separated into two parts, in which the first one is the function of the common electric angle in both signal models, whereas the second part is the function of the electric angle that exists only in near-field signal model. Furthermore, by substituting the common electric angle estimated in the first stage into one special Hermitian matrix formed from another MUSIC spectral function, the range of near-field sources can be obtained from the eigenvector of the Hermitian matrix. The resultant algorithm avoids twodimensional search and pairing parameters; in addition, it avoids the estimation failure problem and alleviates aperture loss. Simulation results are presented to validate the performance of the proposed method. [ABSTRACT FROM AUTHOR]

We correct errors in step 6 of Algorithm 1 given in the paper ‘'Sparse-Group Lasso for Graph Learning from Multi-Attribute Data.’' Other parts of the paper including numerical results are unchanged as the algorithm was implemented correctly. [ABSTRACT FROM AUTHOR]

Detecting periodicity in a short sequence is an important problem, with many applications across science and engineering. Several efficient algorithms have been proposed for this over the years. There is a wide choice available today in terms of the tradeoff between algorithmic complexity and estimation accuracy. In spite of such a rich history, one particular aspect of period estimation has received very little attention from a fundamental perspective. Namely, given a discrete time periodic signal and a list of candidate integer periods, what is the absolute minimum datalength required to estimate its integer period? Notice that the answer we seek must be a fundamental bound, i.e., independent of any particular period estimation technique. Common intuition suggests the minimum datalength as twice the largest expected period. However, this is true only under some special contexts. This paper derives the exact necessary and sufficient bounds to this problem. The above-mentioned question is also extended to the case of mixtures of periodic signals. First, a careful mathematical formulation discussing the unique identifiability of the component periods (hidden integer periods) is presented. Once again, a rigorous theoretical framework in this regard is missing in the existing literature but is a necessary platform to derive precise bounds on the minimum necessary datalength. The bounds given here are generic, that is, independent of the algorithms used. Specific algorithm-dependent bounds are also presented in the end for the case of dictionary-based integer period estimation reported in recent years. [ABSTRACT FROM AUTHOR]

In this paper, a novel augmented complex-valued least-mean kurtosis (ACLMK) algorithm is proposed for processing complex-valued signals. The negated kurtosis of the complex-valued error signal is defined as a cost function by using augmented statistics. As a result of the minimization of this cost function, the ACLMK algorithm containing all second-order statistical properties is obtained for processing noncircular complex-valued signals. Moreover, in this paper, convergence and misadjustment conditions of the proposed ACLMK algorithm are derived from the steady-state analysis. The simulation results on complex-valued system identification, prediction, and adaptive noise cancelling problems show that the use of the cost function defined by the negated kurtosis of the complex-valued error signal based on augmented statistics enables the processing of the noncircular complex-valued signals, and significantly improves the performance of the proposed ACLMK algorithm in terms of the mean square deviation, the mean square error, the prediction gain and the convergence rate when compared to other algorithms. [ABSTRACT FROM AUTHOR]

The Probability Hypothesis Density (PHD) and Cardinalized PHD (CPHD) filters are popular solutions to the multitarget tracking problem due to their low complexity and ability to estimate the number and states of targets in cluttered environments. The PHD filter propagates the first-order moment (i.e. mean) of the number of targets while the CPHD propagates the cardinality distribution in the number of targets, albeit for a greater computational cost. Introducing the Panjer point process, this paper proposes a Second-Order PHD (SO-PHD) filter, propagating the second-order moment (i.e., variance) of the number of targets alongside its mean. The resulting algorithm is more versatile in the modeling choices than the PHD filter, and its computational cost is significantly lower compared to the CPHD filter. This paper compares the three filters in statistical simulations which demonstrate that the proposed filter reacts more quickly to changes in the number of targets, i.e., target births and target deaths, than the CPHD filter. In addition, a new statistic for multiobject filters is introduced in order to study the correlation between the estimated number of targets in different regions of the state space, and propose a quantitative analysis of the spooky effect for the three filters. [ABSTRACT FROM PUBLISHER]

This paper considers stochastic convex optimization problems with two sets of constraints: (a) deterministic constraints on the domain of the optimization variable, which are difficult to project onto; and (b) deterministic or stochastic constraints that admit efficient projection. Problems of this form arise frequently in the context of semidefinite programming as well as when various NP-hard problems are solved approximately via semidefinite relaxation. Since projection onto the first set of constraints is difficult, it becomes necessary to explore projection-free algorithms, such as the stochastic Frank-Wolfe (FW) algorithm. On the other hand, the second set of constraints cannot be handled in the same way, and must be incorporated as an indicator function within the objective function, thereby complicating the application of FW methods. Similar problems have been studied before; however, they suffer from slow convergence rates. This work, equipped with momentum based gradient tracking technique, guarantees fast convergence rates on par with the best-known rates for problems without the second set of constraints. Zeroth-order variants of the proposed algorithms are also developed and again improve upon the state-of-the-art rate results. We further propose the novel trimmed FW variants that enjoy the same convergence rates as their classical counterparts, but are empirically shown to require significantly fewer calls to the linear minimization oracle speeding up the overall algorithm. The efficacy of the proposed algorithms is tested on relevant applications of sparse matrix estimation, clustering via semidefinite relaxation, and uniform sparsest cut problem. [ABSTRACT FROM AUTHOR]

In this paper, we design and analyze Mc2g (Matrix Completion with 2 Graphs), an efficient algorithm that performs matrix completion in the presence of social and item similarity graphs. Mc2g runs in quasilinear time and is parameter free. It is based on spectral clustering and local refinement steps. For the matrix completion problem which possesses additional block structures in its rows and columns, we derive the expected number of sampled entries required for Mc2g to succeed, and further show that it matches an information-theoretic lower bound up to a constant factor for a wide range of parameters. We perform extensive experiments on both synthetic datasets and a semi-real dataset inspired by real graphs. The experimental results show that Mc2g outperforms other state-of-the-art matrix completion algorithms. [ABSTRACT FROM AUTHOR]

This paper studies the 2D localization problem of a sensor network given anchor node positions in a common global coordinate frame and relative position measurements in local coordinate frames between node pairs. It is assumed that the local coordinate frames of different sensors have different orientations and the orientation difference with respect to the global coordinate frame are not known. In terms of graph connectivity, a necessary and sufficient condition is obtained for self-localizability that leads to a fully distributed localization algorithm. Moreover, a distributed verification algorithm is developed to check the graph connectivity condition, which can terminate successfully when the sensor network is self-localizable. Finally, a fully distributed, linear, and iterative algorithm based on the complex-valued Laplacian associated with the sensor network is proposed, which converges globally and gives the correct localization result. [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]

Lattice reduction is a popular preprocessing strategy in multiple-input multiple-output (MIMO) detection. In a quest for developing a low-complexity reduction algorithm for large-scale problems, this paper investigates a new framework called sequential reduction (SR), which aims to reduce the lengths of all basis vectors. The performance upper bounds of the strongest reduction in SR are given when the lattice dimension is no larger than 4. The proposed new framework enables the implementation of a hash-based low-complexity lattice reduction algorithm, which becomes especially tempting when applied to large-scale MIMO detection. Simulation results show that, compared to other reduction algorithms, the hash-based SR algorithm exhibits the lowest complexity while maintaining comparable error performance. [ABSTRACT FROM AUTHOR]

Due to the growth of modern dataset size and the desire to harness computing power of multiple machines, there is a recent surge of interest in the design of distributed machine learning algorithms. However, distributed algorithms are sensitive to Byzantine attackers who can send falsified data to prevent the convergence of algorithms or lead the algorithms to converge to value of the attackers’ choice. Some recent work proposed interesting algorithms that can deal with the scenario when up to half of the workers are compromised. In this paper, we propose a novel algorithm that can deal with an arbitrary number of Byzantine attackers. The main idea is to ask the parameter server to randomly select a small clean dataset and compute noisy gradient using this small dataset. This noisy gradient will then be used as a ground truth to filter out information sent by compromised workers. We show that the proposed algorithm converges to the neighborhood of the population minimizer regardless the number of Byzantine attackers. We further provide numerical examples to show that the proposed algorithm can benefit from the presence of good workers and achieve better performance than existing algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new Bayesian model to solve the Robust PCA problem - recovering the underlying low-rank matrix and sparse matrix from their noisy compositions. We first derive and analyze a new objective function, which is proven to be equivalent to the fundamental objective of minimizing the “rank+sparsity”. To solve this objective, we develop a concise Sparse Bayesian Learning (SBL) method that makes minimal assumptions and effectively deals with the requirements of the problem. The concise modeling allows simple and effective Empirical Bayesian inference via maximum a posteriori expectation-maximization (MAP-EM). We further propose a modified SBL method that additionally utilizes the sparsity pattern information of the outliers in the Robust PCA problem. Simulation studies demonstrate the superiority of the proposed methods over the existing state-of-the-art methods. The efficacy of the proposed methods is further verified through two image processing tasks. [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]

In this paper, we propose a new framework for solving state estimation problems with an additional sparsity-promoting $L_1$ -regularizer term. We first formulate such problems as minimization of the sum of linear or nonlinear quadratic error terms and an extra regularizer, and then present novel algorithms which solve the linear and nonlinear cases. The methods are based on a combination of the iterated extended Kalman smoother and variable splitting techniques such as alternating direction method of multipliers (ADMM). We present a general algorithmic framework for variable splitting methods, where the iterative steps involving minimization of the nonlinear quadratic terms can be computed efficiently by iterated smoothing. Due to the use of state estimation algorithms, the proposed framework has a low per-iteration time complexity, which makes it suitable for solving a large-scale or high-dimensional state estimation problem. We also provide convergence results for the proposed algorithms. The experiments show the promising performance and speed-ups provided by the methods. [ABSTRACT FROM AUTHOR]

In this paper we present a generic framework for the asymptotic performance analysis of subspace-based parameter estimation schemes. It is based on earlier results on an explicit first-order expansion of the estimation error in the signal subspace obtained via an SVD of the noisy observation matrix. We extend these results in a number of aspects. Firstly, we demonstrate that an explicit first-order expansion of the Higher-Order SVD (HOSVD)-based subspace estimate can be derived. Secondly, we show how to obtain explicit first-order expansions of the estimation error of arbitrary ESPRIT-type algorithms and provide the expressions for R-D Standard ESPRIT, R-D Unitary ESPRIT, R-D Standard Tensor-ESPRIT, as well as R-D Unitary Tensor-ESPRIT. Thirdly, we derive closed-form expressions for the mean square error (MSE) and show that they only depend on the second-order moments of the noise. Hence, to apply this framework we only need the noise to be zero mean and possess finite second order moments. Additional assumptions such as Gaussianity or circular symmetry are not needed. [ABSTRACT FROM PUBLISHER]

This paper considers a method for improving physical layer security of wireless networks with full-duplex radio. In particular, fast algorithms are developed to compute power allocations in subcarriers, subject to power and rate constraints, to maximize the secrecy capacity of a three-node network consisting of a source, a full-duplex destination, and an eavesdropper. A residual level of radio self-interference channel is considered. The optimal power allocation at the destination is found to be significant especially when its power budget is high. Also studied in this paper are a network with multiple full-duplex destinations and another network with multiple sources. Using the algorithms developed in this paper, we are able to show that a multiuser strategy that optimizes the power distributions among the users (in terms of either the sources or the destinations) can yield a substantial gain of secrecy capacity over a single-user strategy. [ABSTRACT FROM PUBLISHER]

There are two fundamentally different fronthaul techniques in the downlink communication of cloud radio access network (C-RAN): the data-sharing strategy and the compression-based strategy. Under the former strategy, each user's message is multicast from the central processor (CP) to all the serving remote radio heads (RRHs) over the fronthaul network, which then cooperatively serve the users through joint beamforming; while under the latter strategy, the user messages are first beamformed then quantized at the CP, and the compressed signal is unicast to the corresponding RRH, which then decompresses its received signal for wireless transmission. Previous works show that in general the compression-based strategy outperforms the data-sharing strategy. This paper, on the other hand, points out that in a C-RAN model where the RRHs are connected to the CP via multihop routers, data-sharing can be superior to compression if the network coding technique is adopted for multicasting user messages to the cooperating RRHs, and the RRH's beamforming vectors, the user-RRH association, and the network coding design over the fronthaul network are jointly optimized based on the techniques of sparse optimization and successive convex approximation. This is in comparison to the compression-based strategy, where information is unicast over the fronthaul network by simple routing, and the RRH's compression noise covariance and beamforming vectors, as well as the routing strategy over the fronthaul network are jointly optimized based on the successive convex approximation technique. The observed gain in overall network throughput is due to that information multicast is more efficient than information unicast over the multihop fronthaul of a C-RAN. [ABSTRACT FROM PUBLISHER]

The use of a large-scale antenna array (LSAA) has become an important characteristic of multi-antenna communication systems to achieve beamforming gains such as in designing millimeter-wave (mmWave) systems to combat severe propagation losses. In such applications, each antenna element has to be driven by a radio frequency (RF) chain for the implementation of fully-digital beamformers, significantly increasing the hardware cost, complexity, and power consumption. Therefore, constant-modulus analog beamforming (CMAB) becomes a viable solution. In this paper, we consider the scaled analog beamforming (SAB) or constant-modulus analog beamforming (CMAB) architecture and design the system parameters by solving two variants of beampattern matching problem. In the first case, both the magnitude and phase of the beampattern are matched to the given desired beampattern whereas in the second case, only the magnitude of the beampattern is matched. Both the beampattern matching problems are cast as a variant of the constant-modulus least-squares (CLS) problem. We provide efficient algorithms based on the alternating majorization-minimization (AMM) framework that combines the alternating minimization and the MM frameworks and the conventional-cyclic coordinate descent (C-CCD) algorithms to solve the problem in each case. We also propose algorithms based on a new modified-CCD (M-CCD) based approach. For all the developed algorithms we prove convergence to a Karush-Kuhn-Tucker (KKT) point (or a stationary point). Numerical results demonstrate that the proposed algorithms converge faster than the state-of-the-art solutions. Among all the algorithms, the M-CCD-based algorithms have faster convergence when evaluated in terms of the number of iterations and the AMM-based algorithms offer lower complexity. [ABSTRACT FROM AUTHOR]

Distributed estimation of the average value over a Wireless Sensor Network has recently received a lot of attention. Most papers consider single variable sensors and communications with feedback (e.g., peer-to-peer communications). However, in order to use efficiently the broadcast nature of the wireless channel, communications without feedback are advocated. To ensure the convergence in this feedback-free case, the recently-introduced Sum-Weight-like algorithms which rely on two variables at each sensor are a promising solution. In this paper, the convergence towards the consensus over the average of the initial values is analyzed in depth. Furthermore, it is shown that the squared error decreases exponentially with the time. In addition, a powerful algorithm relying on the Sum-Weight structure and taking into account the broadcast nature of the channel is proposed. [ABSTRACT FROM PUBLISHER]

Adaptive signal detection algorithms in unknown interference are generally formulated under the assumption that training sets are available for the estimation of the test cell interference characteristics. A significant problem occurs in applications such as radar surveillance when the interference covariance matrices of vectors from the training cells and that of the test cell vector are mismatched. False alarm rates may increase beyond acceptable levels and thus overwhelm a receiver if the interference in the test cell is not adequately cancelled. A number of adaptive detection algorithms with the constant false alarm rate (CFAR) property have been designed assuming the availability of training data that have the same covariance matrix as the interference in the test cell (although the adaptive coherence estimator algorithm requires the two covariance matrices to be related by a positive multiplicative constant that is not required to be known). The detection threshold in these CFAR detectors can be selected without knowledge of the interference-plus-noise covariance matrix. To the best of our knowledge, an analytical characterization of the performance effects of a receiver using a mismatched training set (perhaps inadvertently) in adaptive detection is currently not available. This paper addresses the problem analytically. An exact analysis of the effects of interference covariance matrix mismatch on the performance of the adaptive matched filter test is carried out. Results provide insights to the specific aspects of covariance matrix mismatch that cause the increase in false alarms when compared to the matched training set case. Analytical results are illustrated with an example and verified independently with simulations. These results are useful in developing CFAR algorithms under conditions of mismatched training. [ABSTRACT FROM AUTHOR]

In this paper, learning of tree-structured Gaussian graphical models from distributed data is addressed. In our model, samples are stored in a set of distributed machines where each machine has access to only a subset of features. A central machine is then responsible for learning the structure based on received messages from the other nodes. We present a set of communication-efficient strategies, which are theoretically proved to convey sufficient information for reliable learning of the structure. In particular, our analyses show that even if each machine sends only the signs of its local data samples to the central node, the tree structure can still be recovered with high accuracy. Our simulation results on both synthetic and real-world datasets show that our strategies achieve a desired accuracy in inferring the underlying structure while spending a small budget on communication. [ABSTRACT FROM AUTHOR]

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

This paper provides performance bounds for compressed sensing in the presence of Poisson noise using expander graphs. The Poisson noise model is appropriate for a variety of applications, including low-light imaging and digital streaming, where the signal-independent and/or bounded noise models used in the compressed sensing literature are no longer applicable. In this paper, we develop a novel sensing paradigm based on expander graphs and propose a maximum a posteriori (MAP) algorithm for recovering sparse or compressible signals from Poisson observations. The geometry of the expander graphs and the positivity of the corresponding sensing matrices play a crucial role in establishing the bounds on the signal reconstruction error of the proposed algorithm. We support our results with experimental demonstrations of reconstructing average packet arrival rates and instantaneous packet counts at a router in a communication network, where the arrivals of packets in each flow follow a Poisson process. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel approach to perform detection of stochastic signals embedded in an additive random noise. Both signal and noise are considered to be realizations of zero mean random processes of which only second-order statistics are known (their covariance matrices). The method proposed, called constrained stochastic matched filter (CSMF), is an extension of the stochastic matched filter itself derived from the matched filter. The CSMF is optimal in the sense that it maximizes the signal-to-noise ratio in a subspace whose dimension is fixed a priori. In this paper, after giving the reasons for our approach, we show that there is neither an obvious nor analytic solution to the problem expressed. Then an algorithm, which is proved to converge, is proposed to obtain the optimal solution. Evaluation of the algorithm's performance is completed through estimation of receiver operating characteristic curves. Experiments on real signals show the improvement brought about by this method and thus its significance. [ABSTRACT FROM AUTHOR]

One main drawback of using time difference of arrival (TDOA) methods for source localization and navigation is that they require centralization of multiple copies of a signal. This paper considers blindly estimating the location of a cyclic prefix (CP) in an orthogonal frequency division multiplexing (OFDM) signal, enabling distributed TDOA computation up to an integer ambiguity. This ambiguity can be resolved using integer least-squares methods, if enough TDOAs are available, requiring only minimal cooperation between receivers. The contributions of this paper are development of an algorithm for simultaneously resolving the integer ambiguities and obtaining a position estimate; and derivation of the Cramér–Rao lower bound (CRLB) on locating the CP, and hence, on the underlying source localization and navigation problems. [ABSTRACT FROM AUTHOR]

Channel state information (CSI) at the base station (BS) is crucial to achieve beamforming and multiplexing gains in multiple-input multiple-output (MIMO) systems. State-of-the-art limited feedback schemes require feedback overhead that scales linearly with the number of BS antennas, which is prohibitive for 5G massive MIMO. This paper proposes novel limited feedback algorithms that lift this burden by exploiting the inherent sparsity in double-directional MIMO channel representation using overcomplete dictionaries. These dictionaries are associated with angle of arrival and angle of departure that specifically account for antenna directivity patterns at both ends of the link. The proposed algorithms achieve satisfactory channel estimation accuracy using a small number of feedback bits, even when the number of transmit antennas at the BS is large—making them ideal for 5G massive MIMO. Judicious simulations reveal that they outperform a number of popular feedback schemes and underscore the importance of using angle dictionaries matching the given antenna directivity patterns, as opposed to uniform dictionaries. The proposed algorithms are lightweight in terms of computation, especially on the user equipment side, making them ideal for actual deployment in 5G systems. [ABSTRACT FROM AUTHOR]

This paper studies the stochastic behavior of the LMS and NLMS algorithms in a system identification framework for a cyclostationary white input without assuming a Gaussian distribution for the input. The input cyclostationary signal is modeled by a white random process with periodically time-varying power. The system parameters vary according to a random-walk. Mathematical models are derived for the mean and mean-square-deviation behavior of the adaptive weights as a function of the input cyclostationarity. Analytical models are first derived for the LMS and NLMS algorithms for cyclostationary white inputs. These models show the dependence of the two algorithms upon the kurtosis of the input. Significant differences are found between the behaviors of the two algorithms when the analysis is applied to non-Gaussian cases. Monte Carlo simulations provide strong support for the theory. [ABSTRACT FROM AUTHOR]

In this paper, we consider the case in which one needs to carry out Gabor analysis and synthesis on large signals using a short support analysis window and its corresponding, possibly longer canonical dual window, respectively. In this asymmetric context, we propose a novel factorization of the Gabor frame operator that exploits its strong and well-known structure and leads to a computational cost for synthesis, which is comparable to the one needed for short support analysis. The proposed factorization applies to any Gabor system with very mild conditions and leads to a potentially promising alternative to current synthesis algorithms in the case of short analysis windows whose support is slightly above the number of frequency channels. [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]

This paper introduces Bayes risk (expected loss) as a criterion for linear equalization. Since the probability of error is equal to the Bayes risk (BR) for a particular binary loss function, this work is a natural generalization of previous works on minimum probability of error (PE) equalizers. Adaptive equalization algorithms are developed that minimize the BR. Like the minimum PE equalizers, the BR algorithms have low computational complexity which is comparable to that of the LMS algorithm. The advantage of the BR criterion is that the loss function can be specified in a manner that accelerates adaptive equalizer convergence relative to the minimum PE adaptive algorithm as illustrated in simulation examples. Besides introducing a new criterion, this paper provides another independent contribution to the field of PE minimizing equalization. While most prior works focus on M-ary QAM type modulations with rectangular decision regions, this paper uses upper bounds on the probabilities of certain events to yield tractable mathematics that apply to two-dimensional constellations with arbitrarily shaped decision regions. The resulting adaptive algorithm use the full information available in the phase of the error signal, whereas previous algorithms use a quantized version of this error phase. [ABSTRACT FROM AUTHOR]