Search

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]

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

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]

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]

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]

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]

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]

While many distributed optimization algorithms have been proposed for solving smooth or convex problems over the networks, few of them can handle non-convex and non-smooth problems. Based on a proximal primal-dual approach, this paper presents a new (stochastic) distributed algorithm with Nesterov momentum for accelerated optimization of non-convex and non-smooth problems. Theoretically, we show that the proposed algorithm can achieve an $\epsilon$ -stationary solution under a constant step size with $\mathcal {O}(1/\epsilon ^2)$ computation complexity and $\mathcal {O}(1/\epsilon)$ communication complexity when the epigraph of the non-smooth term is a polyhedral set. When compared to the existing gradient tracking based methods, the proposed algorithm has the same order of computation complexity but lower order of communication complexity. To the best of our knowledge, the presented result is the first stochastic algorithm with the $\mathcal {O}(1/\epsilon)$ communication complexity for non-convex and non-smooth problems. Numerical experiments for a distributed non-convex regression problem and a deep neural network based classification problem are presented to illustrate the effectiveness of the proposed algorithms. [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 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]

This paper presents algorithms for the parallelization of inference in hidden Markov models (HMMs). In particular, we propose a parallel forward-backward type of filtering and smoothing algorithm as well as a parallel Viterbi-type maximum-a-posteriori (MAP) algorithm. We define associative elements and operators to pose these inference problems as all-prefix-sums computations and parallelize them using the parallel-scan algorithm. The advantage of the proposed algorithms is that they are computationally efficient in HMM inference problems with long time horizons. We empirically compare the performance of the proposed methods to classical methods on a highly parallel graphics processing unit (GPU). [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]

In this paper, we investigate designs of linear precoders for vector Gaussian channels via stochastic optimizations and deep neural networks (DNNs). We assume that the channel inputs are drawn from practical finite alphabets, and we search for precoders maximizing the mutual information between channel inputs and outputs. Though the problem is generally non-convex, we prove that when the right singular matrix of precoder is fixed, any local optima of this problem is a global optima. Based on this fact, an efficient projected stochastic gradient descent (PSGD) algorithm is designed to search the optimal precoders. Moreover, to reduce the complexity of calculating a posterior means involved in gradients calculation, K-best algorithm is adopted to make approximations of a posterior means with negligible loss of accuracy. Furthermore, to avoid explicit calculation of mutual information and its gradients, DNN-based autoencoders (AEs) are constructed for this precoding task, and an efficient training algorithm is proposed. We also prove that the AEs, with ‘softmax’ activation function and ‘categorical cross entropy’ loss, maximize the mutual information under reasonable assumptions. Then, in order to extend the AE methods to large scale systems, ‘sigmoid’ activation function and ‘binary cross entropy’ loss are used such that the size of AEs will not grow prohibitively large. We prove that this maximizes a lower bound of the mutual information under reasonable assumptions. Finally, to make the precoders practical for high speed wireless scenarios, we propose an offline training paradigm which trains DNNs to infer optimal precoders given channel state information instead of training online for every different channel. Simulation results show that all the proposed methods work well in maximizing mutual information and improving bit error rate (BER) performance. [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]

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 consider maximum-likelihood (ML) MIMO detection under one-bit quantized observations and binary symbol constellations. This problem is motivated by the recent interest in adopting coarse quantization in massive MIMO systems—as an effective way to scale down the hardware complexity and energy consumption. Classical MIMO detection techniques consider unquantized observations, and many of them are not applicable to the one-bit MIMO case. We develop a new non-convex optimization algorithm for the one-bit ML MIMO detection problem, using a strategy called homotopy optimization. The idea is to transform the ML problem into a sequence of approximate problems, from easy (convex) to hard (close to ML), and with each problem being a gradual modification of its previous. Then, our attempt is to iteratively trace the solution path of these approximate problems. This homotopy algorithm is well suited to the application of deep unfolding, a recently popular approach for turning certain model-based algorithms into data-driven, and performance enhanced, ones. While our initial focus is on one-bit MIMO detection, the proposed technique also applies naturally to the classical unquantized MIMO detection. We performed extensive simulations and show that the proposed homotopy algorithms, both non-deep and deep, have satisfactory bit-error probability performance compared to many state-of-the-art algorithms. Also, the deep homotopy algorithm has attractively low computational complexity. [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]

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]

Direction of arrival (DOA) estimation is a classical topic in source localization. Notably, a reliable grid-free sparse representation algorithm, called FRI (finite rate of innovation) algorithm, was proposed to recover the finite number of Dirac pulses from a stream of 1D temporal samples, which also offers a efficient solution to the DOA estimation problem. Typically, FRI method assumes uniform sampling with single snapshot. However, the actual situation is richer and more diverse. Motivated by the requests of practical applications (e.g. array deployment, algorithm run-speed, etc.), a generic FRI method is proposed to tackle the more general case in practice, i.e. non-uniform sampling with multiple snapshots. Instead of annihilating the measured sensor data, a model-fitting method is used to robustly retrieve the sparse representation (i.e. DOAs and associated amplitudes) of the 1D samples. We demonstrate that our algorithm can handle challenging DOA tasks with high-resolution, which we validate in various conditions, such as multiple coherent sources, insufficient signal snapshots, low signal-to-noise ratio (SNR), etc. Moreover, we show that the computational complexity of our algorithm mainly scales with the number of sources and varies very slowly with the number of samples and snapshots, which meets the needs of a wider range of practical applications. [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]

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]

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]

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]

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]

Inference of space-time varying signals on graphs emerges naturally in a plethora of network science related applications. A frequently encountered challenge pertains to reconstructing such dynamic processes, given their values over a subset of vertices and time instants. The present paper develops a graph-aware kernel-based kriged Kalman filter that accounts for the spatio-temporal variations, and offers efficient online reconstruction, even for dynamically evolving network topologies. The kernel-based learning framework bypasses the need for statistical information by capitalizing on the smoothness that graph signals exhibit with respect to the underlying graph. To address the challenge of selecting the appropriate kernel, the proposed filter is combined with a multikernel selection module. Such a data-driven method selects a kernel attuned to the signal dynamics on-the-fly within the linear span of a preselected dictionary. The novel multikernel learning algorithm exploits the eigenstructure of Laplacian kernel matrices to reduce computational complexity. Numerical tests with synthetic and real data demonstrate the superior reconstruction performance of the novel approach relative to state-of-the-art alternatives. [ABSTRACT FROM AUTHOR]

The demand for accurate localization in complex environments continues to increase despite the difficulty in extracting positional information from measurements. Conventional range-based localization approaches rely on distance estimates obtained from measurements (e.g., delay or strength of received waveforms). This paper goes one step further and develops localization techniques that rely on all probable range values rather than on a single estimate of each distance. In particular, the concept of soft range information (SRI) is introduced, showing its essential role for network localization. We then establish a general framework for SRI-based localization and develop algorithms for obtaining the SRI using machine learning techniques. The performance of the proposed approach is quantified via network experimentation in indoor environments. The results show that SRI-based localization techniques can achieve performance approaching the Cramér–Rao lower bound and significantly outperform the conventional techniques especially in harsh wireless environments. [ABSTRACT FROM AUTHOR]

This paper proposes an online multiple object tracker that can operate under unknown detection profile and clutter rate. In a majority of multiple object tracking applications, model parameters for background processes such as clutter and detection are unknown and vary with time; hence, the ability of the algorithm to adaptively learn these parameters is essential in practice. In this paper, we detail how the generalized labeled multibernoulli filter, a tractable and provably Bayes optimal multiobject tracker, can be tailored to learn clutter and detection parameters on-the-fly while tracking. Provided that these background model parameters do not fluctuate rapidly compared to the data rate, the proposed algorithm can adapt to the unknown background yielding better tracking performance. [ABSTRACT FROM AUTHOR]

Grant-free random access is a promising protocol to support massive access in beyond fifth-generation (B5G) cellular Internet-of-Things (IoT) with sporadic traffic. Specifically, in each coherence interval, the base station (BS) performs joint activity detection and channel estimation (JADCE) before data transmission. Due to the deployment of a large-scale antennas array and the existence of a huge number of IoT devices, JADCE usually has high computational complexity and needs long pilot sequences. To solve these challenges, this paper proposes a dimension reduction method, which projects the original device state matrix to a low-dimensional space by exploiting its sparse and low-rank structure. Then, we develop an optimized design framework with a coupled full column rank constraint for JADCE to reduce the size of the search space. However, the resulting problem is non-convex and highly intractable, for which the conventional convex relaxation approaches are inapplicable. To this end, we propose a logarithmic smoothing method for the non-smoothed objective function and transform the interested matrix to a positive semidefinite matrix, followed by giving a Riemannian trust-region algorithm to solve the problem in complex field. Simulation results show that the proposed algorithm is efficient to a large-scale JADCE problem and requires shorter pilot sequences than the state-of-art algorithms which only exploit the sparsity of device state matrix. [ABSTRACT FROM AUTHOR]

In recent years, the sources localization has noticed an increase in research conducted on the problem of mixed far-field sources (FFSs) and near-field sources (NFSs). The main assumption of the existing researches is that the signals should be uncorrelated. Therefore, they cannot be used for multipath environments. The present paper provides a method called components separation algorithm (CSA) for the localization of multiple mixed FFSs and NFSs, including uncorrelated, lowly correlated and coherent signals. Firstly, by constructing one special cumulant matrix, and using a MUSIC-based technique, the noncoherent DOA vector (NDOAV) is extracted. By constructing another special cumulant matrix, and with respect to NDOAV, an estimate of the range, as well as a signal classification is obtained for noncoherent sources. Then, by estimating their kurtosis, the noncoherent component and consequently the coherent one of the second cumulant matrix is obtained. Finally, by introducing a novel approach based on squaring, projection, spatial smoothing, array interpolation transform and coherent component restoring, the parameters of coherent signals in each coherent group are estimated separately. The CSA prevents severe loss of the aperture. Furthermore, it does not require any pairing. The simulation results validate its satisfactory performance in terms of estimation accuracy, resolution, computational complexity, reasonable classification, and also its robustness against lowly correlated sources. [ABSTRACT FROM AUTHOR]

Dictionary learning (DL) is a well-researched problem, where the goal is to learn a dictionary from a finite set of noisy training signals, such that the training data admits a sparse representation over the dictionary. While several solutions are available in the literature, relatively little is known about their convergence and optimality properties. In this paper, we make progress on this problem by analyzing a Bayesian algorithm for DL. Specifically, we cast the DL problem into the sparse Bayesian learning (SBL) framework by imposing a hierarchical Gaussian prior on the sparse vectors. This allows us to simultaneously learn the dictionary as well as the parameters of the prior on the sparse vectors using the expectation-maximization algorithm. The dictionary update step turns out to be a non-convex optimization problem, and we present two solutions, namely, an alternating minimization (AM) procedure and an Armijo line search (ALS) method. We analytically show that the ALS procedure is globally convergent, and establish the stability of the solution by characterizing its limit points. Further, we prove the convergence and stability of the overall DL-SBL algorithm, and show that the minima of the cost function of the overall algorithm are achieved at sparse solutions. As a concrete example, we consider the application of the SBL-based DL algorithm to image denoising, and demonstrate the efficacy of the algorithm relative to existing DL algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we develop a kernel adaptive filter for quaternion data, using stochastic information gradient (SIG) cost function based on the information theoretic learning (ITL) approach. The new algorithm (QKSIG) is useful for quaternion-based kernel applications of nonlinear filtering. Adaptive filtering in quaterion domain intrinsically incorporates component-wise real valued cross-correlation or the coupling within the dimensions of the quaternion input. We apply generalized Hamilton-real (GHR) calculus that is applicable to quaternion Hilbert space for evaluating the cost function gradient. The QKSIG algorithm minimizes Shannon's entropy of the error between the filter output and desired response and minimizes the divergence between the joint densities of input-desired and input-output pairs. The SIG technique reduces the computational complexity of the error entropy estimation. Here, ITL with SIG approach is applied to quaternion adaptive filtering for three different reasons. First, it reduces the algorithm computational complexity compared to our previous work quaternion kernel minimum error entropy algorithm (QKMEE). Second, it improves the filtering performance by considering the coupling within the dimensions of the quaternion input. Third, it performs better in biased or non-Gaussian signal and noise environments due to ITL approach. We present convergence analysis and steady-state performance analysis results of the new algorithm (QKSIG). Simulation results are used to show the behavior of the new algorithm QKSIG in quaternion non-Gaussian signal and noise environments compared to the existing ones such as quadruple real-valued kernel stochastic information gradient (KSIG) and quaternion kernel LMS (QKLMS) 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]

We propose a novel adaptive kernel-based regression method for complex-valued signals: the generalized complex-valued kernel least-mean-square (gCKLMS). We borrow from the new results on widely linear reproducing kernel Hilbert space (WL-RKHS) for nonlinear regression and complex-valued signals, recently proposed by the authors. This paper shows that in the adaptive version of the kernel regression for complex-valued signals we need to include another kernel term, the so-called pseudo-kernel. This new solution is endowed with better representation capabilities in complex-valued fields since it can efficiently decouple the learning of the real and the imaginary part. Also, we review previous realizations of the complex KLMS algorithm and its augmented version to prove that they can be rewritten as particular cases of the gCKLMS. Furthermore, important conclusions on the design of the kernels are drawn that help to greatly improve the convergence of the algorithms. In the experiments, we revisit the nonlinear channel equalization problem to highlight the better convergence of the gCKLMS compared to previous solutions. Also, the flexibility of the proposed generalized approach is tested in a second experiment with non-independent real and imaginary parts. The results illustrate the significant performance improvements of the gCKLMS approach when the complex-valued signals have different properties for the real and imaginary parts. [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]