Search

Hammerstein model with a static nonlinearity followed by a linear filter is commonly used in numerous applications. This paper focuses on adaptive filtering techniques for parameter identification of Hammerstein systems and output prediction of nonlinear systems. By formulating the underlying filtering problem as a recursive bilinear least-squares optimization with the non-convex feasible region constraint, we develop a recursive non-convex projected least-squares (RncPLS) algorithm based on alternating direction method of multipliers (ADMM). The RncPLS algorithm alternates between implementing ridge regression and projecting on the non-convex feasible set, which successively refines the system parameters. The convergence and accuracy properties of the proposed RncPLS algorithm are theoretically investigated. Moreover, extensive simulation results in the context of system identification, nonlinear predication, and acoustic echo cancellation, are also included to demonstrate the performance characteristics of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Sensor placement methods for field estimation based on Gaussian processes are proposed. Generally, sensor placement methods determine the appropriate placement positions by selecting them from predefined candidate positions. Many criteria for the selection have been proposed, with which the quality of the placements is evaluated with regard to the field at the candidate positions. This means that these sensor placement methods seek to find the positions that can estimate the field at the candidate positions accurately. In practical situations, however, the candidate sensor placement region can be different from the target region for field estimation. In this paper, to make sensor placement methods applicable to this situation, we propose two sensor placement methods based on the mean squared error and on conditional entropy that can be applied to cases in which the sensor placement region is arbitrarily restricted. After formulating the sensor placement problems, two approximate algorithms are derived: the greedy algorithm and the convex-relaxation-based algorithm. The application of the proposed methods to sound field estimation is also illustrated, and their effectiveness was confirmed through numerical experiments. [ABSTRACT FROM AUTHOR]

Data representation techniques have made a substantial contribution to advancing data processing and machine learning (ML). Improving predictive power was the focus of previous representation techniques, which unfortunately perform rather poorly on the interpretability in terms of extracting underlying insights of the data. Recently, the Kolmogorov model (KM) was studied, which is an interpretable and predictable representation approach to learning the underlying probabilistic structure of a set of random variables. The existing KM learning algorithms using semi-definite relaxation with randomization (SDRwR) or discrete monotonic optimization (DMO) have, however, limited utility to big data applications because they do not scale well computationally.In this paper, we propose a computationally scalable KM learning algorithm, based on the regularized dual optimization combined with enhanced gradient descent (GD) method. To make our method more scalable to large-dimensional problems, we propose two acceleration schemes, namely, the eigenvalue decomposition (EVD) elimination strategy and an approximate EVD algorithm. Furthermore, a thresholding technique by exploiting the error bound analysis and leveraging the normalized Minkowski $\ell _1$ -norm, is provided for the selection of the number of iterations of the approximate EVD algorithm. When applied to big data applications, it is demonstrated that the proposed method can achieve compatible training/prediction performance with significantly reduced computational complexity; roughly two orders of magnitude improvement in terms of the time overhead, compared to the existing KM learning algorithms. Furthermore, it is shown that the accuracy of logical relation mining for interpretability by using the proposed KM learning algorithm exceeds 80%. [ABSTRACT FROM AUTHOR]

Motivated by the recent success of reinforcement learning algorithms, this paper studies a class of biased stochastic approximation (SA) procedures under a mild “ergodicity-like” assumption on the random noise sequence. Building on a multistep Lyapunov function that looks ahead to several future updates to accommodate the stochastic perturbations (thus gaining control over the bias), we prove a general result on the convergence of the SA iterates, and use it to derive non-asymptotic bounds on the mean-square error in the case of constant stepsizes. This novel viewpoint renders finite-time analysis of biased SA algorithms under a family of stochastic perturbations possible. For direct comparison with prior work, we demonstrate these bounds by applying them to TD-learning with linear function approximation, under the Markov chain observation model. The resultant finite-time error bound for TD-learning is the first of its kind, in the sense that it holds i) for the unmodified versions (i.e., without any modification to the updates) using even nonlinear approximators; as well as for Markov chains ii) under sublinear mixing conditions and iii) starting from any initial distribution, at least one of which has to be violated for existing results to be applicable. [ABSTRACT FROM AUTHOR]

Constrained reinforcement learning (CRL), also termed as safe reinforcement learning, is a promising technique enabling the deployment of RL agent in real-world systems. In this paper, we propose a successive convex approximation based off-policy optimization (SCAOPO) algorithm to solve the general CRL problem, which is formulated as a constrained Markov decision process (CMDP) in context of the average cost. The SCAOPO is based on solving a sequence of convex objective/feasibility optimization problems obtained by replacing the objective and constraint functions in the original problem with convex surrogate functions. The proposed SCAOPO enables reuse of experiences from previous updates, thereby significantly reducing implementation cost when deployed in real-world engineering systems that need to online learn the environment. In spite of the time-varying state distribution and the stochastic bias incurred by off-policy learning, the SCAOPO with a feasible initial point can still provably converge to a Karush-Kuhn-Tucker (KKT) point of the original problem almost surely. [ABSTRACT FROM AUTHOR]

One-bit compressive sensing gains its popularity in signal processing and communications due to its low storage costs and low hardware complexity. However, it has been a challenging task to recover the signal only by exploiting the one-bit (the sign) information. In this paper, we appropriately formulate the one-bit compressive sensing into a double-sparsity constrained optimization problem. The first-order optimality conditions for this nonconvex and discontinuous problem are established via the newly introduced $\tau$ -stationarity, based on which, a gradient projection subspace pursuit (GPSP) algorithm is developed. It is proven that GPSP can converge globally and terminate within finite steps. Numerical experiments have demonstrated its excellent performance in terms of a high order of accuracy with a high computational speed. [ABSTRACT FROM AUTHOR]

Angular path integration is the ability of a system to estimate its own heading direction from potentially noisy angular velocity (or increment) observations. Non-probabilistic algorithms for angular path integration, which rely on a summation of these noisy increments, do not appropriately take into account the reliability of such observations, which is essential for appropriately weighing one’s current heading direction estimate against incoming information. In a probabilistic setting, angular path integration can be formulated as a continuous-time nonlinear filtering problem (circular filtering) with observed state increments. The circular symmetry of heading direction makes this inference task inherently nonlinear, thereby precluding the use of popular inference algorithms such as Kalman filters, rendering the problem analytically inaccessible. Here, we derive an approximate solution to circular continuous-time filtering, which integrates state increment observations while maintaining a fixed representation through both state propagation and observational updates. Specifically, we extend the established projection-filtering method to account for observed state increments and apply this framework to the circular filtering problem. We further propose a generative model for continuous-time angular-valued direct observations of the hidden state, which we integrate seamlessly into the projection filter. Applying the resulting scheme to a model of probabilistic angular path integration, we derive an algorithm for circular filtering, which we term the circular Kalman filter. Importantly, this algorithm is analytically accessible, interpretable, and outperforms an alternative filter based on a Gaussian approximation. [ABSTRACT FROM AUTHOR]

We introduce a novel method for online smoothing in state-space models that utilises a fixed-lag approximation to overcome the well known issue of path degeneracy. Unlike classical fixed-lag techniques that only approximate certain marginals, we introduce an online resampling algorithm, called particle stitching, that converts these marginal samples into a full posterior approximation. We demonstrate the utility of our method in the context of map-matching, the task of inferring a vehicle’s trajectory given a road network and noisy GPS observations. We develop a new state-space model for the difficult task of map-matching on dense, urban road networks. [ABSTRACT FROM AUTHOR]

Optimizing non-convex functions is of primary importance in modern pattern recognition because it underlies the training of deep networks and nonlinear dimensionality reduction. First-order algorithms under suitable randomized perturbations or step-size rules have been shown to be effective for such settings as their limit points can be guaranteed to be local extrema rather than saddle points. However, it is well-known that the practical convergence of first-order methods is slower than those which exploit additional structure. In particular, empirically, successive convex approximation (SCA) converges faster than first-order methods. However, to date, SCA in general non-convex settings converges to first-order stationary points, which could either be local extrema or saddle points whose performance is typically inferior. To mitigate this issue, we propose calibrated randomized perturbations of SCA, which exhibit the improved convergence rate as compared to the gradient descent counter part. In particular, our main technical contributions are to establish the non-asymptotic performance of SCA algorithm and its perturbed variant converges to an approximate second-order stationary point. Experiments on multi-dimensional scaling, a machine learning problem whose training objective is non-convex, substantiate the performance gains associated with employing random perturbations. [ABSTRACT FROM AUTHOR]

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

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

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

Partitioned-block frequency-domain adaptive filter (PBFDAF) algorithms have become very popular, in particular, for acoustic signal processing. However, the stochastic behavior of PBFDAFs has not been extensively examined. This paper presents a comprehensive statistical analysis for a family of the overlap-save PBFDAF algorithms with 50% overlap, including the transient and steady-state performance. The frequency-domain equations of the PBFDAFs are transformed into the time-domain counterparts, which allows us to carry out the analysis completely in the time domain. By means of the independence assumption and vectorization operation, theoretical models for the mean and mean-square behavior of the PBFDAF algorithms are established without restricting the distribution of the inputs to being Gaussian. Specifically, the mean weight behavior and corresponding steady-state solution are provided. Closed-form expressions for the mean-square deviation (MSD) and mean-square error (MSE) are derived. The upper bound on the step size for the mean and mean-square stability of the PBFDAFs is specified. The theoretical model presents new insights into the convergence properties of the PBFDAFs with a sufficient number of coefficients. It was revealed that both the constrained and unconstrained PBFDAFs converge to the Wiener solution. However, the mean weight vector of the unconstrained PBFDAF algorithms cannot converge to the true solution for any inputs, while that of the constrained version can. The presented theory explains why the steady-state MSD of the unconstrained PBFDAF algorithm is larger than that of the constrained version but their minimum MSE is the same. Monte Carlo simulations provide very good support for our theory. [ABSTRACT FROM AUTHOR]

This paper introduces a collection of scaling methods for generating $\text{2}\,N$ -point DCT-II approximations based on $N$ -point low-complexity transformations. Such scaling is based on the Hou recursive matrix factorization of the exact $\text{2}\,N$ -point DCT-II matrix. Encompassing the widely employed Jridi-Alfalou-Meher scaling method, the proposed techniques are shown to produce DCT-II approximations that outperform the transforms resulting from the JAM scaling method according to total error energy and mean squared error. Orthogonality conditions are derived and an extensive error analysis based on statistical simulation demonstrates the good performance of the introduced scaling methods. A hardware implementation is also provided demonstrating the competitiveness of the proposed methods when compared to the JAM scaling method. [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]

An analytic parahermitian matrix admits an eigenvalue decomposition (EVD) with analytic eigenvalues and eigenvectors except in the case of multiplexed data. In this paper, we propose an iterative algorithm for the estimation of the analytic eigenvalues. Since these are generally transcendental, we find a polynomial approximation with a defined error. Our approach operates in the discrete Fourier transform (DFT) domain and for every DFT length generates a maximally smooth association through EVDs evaluated in DFT bins; an outer loop iteratively grows the DFT order and is shown, in general, to converge to the analytic eigenvalues. In simulations, we compare our results to existing approaches. [ABSTRACT FROM AUTHOR]

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

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

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

Standard Principal-Component Analysis (PCA) is known to be sensitive to outliers among the processed data. On the other hand, L1-norm-based PCA (L1-PCA) exhibits sturdy resistance against outliers, while it performs similar to standard PCA when applied to nominal or smoothly corrupted data. Exact calculation of the K L1-norm Principal Components (L1-PCs) of a rank-r data matrix X ∈ RD × N costs O(N(r −1)K + 1). In this work, we present reduced-rank L1-PCA (RR L1-PCA): a hybrid approach that approximates the K L1-PCs of X by the L1-PCs of its L2-norm-based rank-d approximation (d ≤ r), calculable exactly with reduced complexity O(N(d − 1)K + 1). The proposed method combines the denoising capabilities and low computation cost of standard PCA with the outlier-resistance of L1-PCA. RR L1-PCA is accompanied by formal performance guarantees as well as thorough numerical studies that corroborate its computational and corruption resistance merits. [ABSTRACT FROM AUTHOR]

We propose an entirely redesigned framework of bandlimited signal reconstruction for the time encoding machine (TEM) introduced by Lazar and Tóth. As the encoding part of TEM consists in obtaining integral values of a bandlimited input over known time intervals, it theoretically amounts to applying a known linear operator on the input. We then approach the general question of signal reconstruction by pseudo-inversion of this operator. We perform this task numerically and iteratively using projections onto convex sets (POCS). The algorithm can be implemented exactly in discrete time with multiplications that are all reduced to scaling by signed powers of two, thanks to the use of relaxation coefficients. Meanwhile, the algorithm achieves a rate of convergence similar to that of Lazar and Tóth. For real-time processing, we propose an approximate time-varying FIR implementation, which avoids the splitting of the input into blocks. We finally propose some preliminary semi-convergence analysis of the algorithm under data noise. [ABSTRACT FROM AUTHOR]

This paper proposes a computationally efficient algorithm for distributed fusion in a sensor network in which multi-Bernoulli (MB) filters are locally running in every sensor node for multi-object tracking. The generalized Covariance Intersection (GCI) fusion rule is employed to fuse multiple MB random finite set densities. The fused density comprises a set of fusion hypotheses that grow exponentially with the number of Bernoulli components. Thus, GCI fusion with MB filters can become computationally intractable in practical applications that involve tracking of even a moderate number of objects. In order to accelerate the multi-sensor fusion procedure, we derive a theoretically sound approximation to the fused density. The number of fusion hypotheses in the resulting density is significantly smaller than the original fused density. It also has a parallelizable structure that allows multiple clusters of Bernoulli components to be fused independently. By carefully clustering Bernoulli components into isolated clusters using the GCI divergence as the distance metric, we propose an alternative to build exactly the approximated density without exhaustively computing all the fusion hypotheses. The combination of the proposed approximation technique and the fast clustering algorithm can enable a novel and fast GCI-MB fusion implementation. Our analysis shows that the proposed fusion method can dramatically reduce the computational and memory requirements with small bounded $L_1$ -error. The Gaussian mixture implementation of the proposed method is also presented. In various numerical experiments, including a challenging scenario with up to forty objects, the efficacy of the proposed fusion method is demonstrated. [ABSTRACT FROM AUTHOR]

Sequences with low autocorrelation sidelobes are needed in a diverse set of active sensing applications, including radar, sonar, communications, and biomedicine. The recently proposed and widely adopted methods of the Cyclic Algorithm-New (CAN) and Periodic CAN (PeCAN) are known to be computationally efficient, particularly as they employ fast Fourier transform (FFT) operations to design unimodular (i.e., unit-modulus) sequences with good autocorrelation properties. However, these cyclic algorithms cannot be directly used to design binary sequences with good autocorrelation properties due to the extremely multimodal nature of the associated optimization objectives. In this paper, we combine the notion of converging functions with the CAN and PeCAN frameworks, to considerably enhance their performances for binary sequence synthesis. Moreover, the convergence of these algorithms are established and their convergence properties are thoroughly analyzed. Numerical examples are provided to show that the proposed algorithms can outperform existing approaches for aperiodic and periodic binary sequence synthesis, especially for long sequence designs. [ABSTRACT FROM AUTHOR]

We consider the problem of detecting abrupt changes in the underlying stochastic structure of multivariate signals. A novel non-parametric and model-free off-line change-point detection method based on a kernel mapping is presented. This approach is sequential and alternates between two steps: a greedy detection to estimate a new breakpoint and a projection to remove its contribution to the signal. The resulting algorithm is able to segment time series for which no accurate model is available: it is computationally more efficient than exact kernel change-point detection and more precise than window-based approximations. The proposed method also offers some theoretical consistency properties. For the special case of a linear kernel, an even faster implementation is provided. The proposed strategy is compared to standard parametric and non-parametric procedures on a real-world data set composed of 262 accelerometer recordings. [ABSTRACT FROM AUTHOR]

Frequency-resolved optical gating (FROG) is a popular technique for complete characterization of ultrashort laser pulses. The acquired data in FROG, called FROG trace, is the Fourier magnitude of the product of the unknown pulse with a time-shifted version of itself, for several different shifts. To estimate the pulse from the FROG trace, we propose an algorithm that minimizes a smoothed non-convex least-squares objective function. The method consists of two steps. First, we approximate the pulse by an iterative spectral algorithm. Then, the attained initialization is refined based upon a sequence of block stochastic gradient iterations. The algorithm is theoretically simple, numerically scalable, and easy-to-implement. Empirically, our approach outperforms the state-of-the-art when the FROG trace is incomplete, that is, when only few shifts are recorded. Simulations also suggest that the proposed algorithm exhibits similar computational cost compared to a state-of-the-art technique for both complete and incomplete data. In addition, we prove that in the vicinity of the true solution, the algorithm converges to a critical point. A Matlab implementation is publicly available at https://github.com/samuelpinilla/FROG. [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]

Orthogonal greedy algorithms are popular sparse signal reconstruction algorithms. Their principle is to select atoms one by one. A series of unconstrained least-square subproblems of gradually increasing size is solved to compute the approximation coefficients, which is efficiently performed using a fast recursive update scheme. When dealing with non-negative sparse signal reconstruction, a series of non-negative least-squares subproblems have to be solved. Fast implementation becomes tricky since each subproblem does not have a closed-form solution anymore. Recently, non-negative extensions of the classical orthogonal matching pursuit and orthogonal least squares algorithms were proposed, using slow (i.e., non-recursive) or recursive but inexact implementations. In this paper, we revisit these algorithms in a unified way. We define a class of non-negative orthogonal greedy algorithms and exhibit their structural properties. We propose a fast and exact implementation based on the active-set resolution of non-negative least-squares and exploiting warm start initializations. The algorithms are assessed in terms of accuracy and computational complexity for a sparse spike deconvolution problem. We also present an application to near-infrared spectra decomposition. [ABSTRACT FROM AUTHOR]

We present a novel algorithm, an adaptive-lag smoother, approximating efficiently, in an online fashion, sequences of expectations under the marginal smoothing distributions in general state-space models. The algorithm evolves recursively a bank of estimators, one for each marginal, in resemblance with the so-called particle-based, rapid incremental smoother (PaRIS). Each estimator is propagated until a stopping criterion, measuring the fluctuations of the estimates, is met. The presented algorithm is furnished with theoretical results describing its asymptotic limit and memory usage. [ABSTRACT FROM AUTHOR]

Many resource allocation tasks are challenging global (i.e., non-convex) optimization problems. The main issue is that the computational complexity of these problems grows exponentially in the number of variables instead of polynomially as for many convex optimization problems. However, often the non-convexity stems only from a subset of variables. Conventional global optimization frameworks like monotonic optimization or DC programming treat all variables as global variables and require complicated, problem specific decomposition approaches to exploit the convexity in some variables. To overcome this challenge, we develop an easy-to-use algorithm that inherently differentiates between convex and non-convex variables, preserving the low computational complexity in the number of convex variables. Another issue with these widely used frameworks is that they may suffer from severe numerical problems. We discuss this issue in detail and provide a clear motivating example. The solution to this problem is to replace the traditional approach of finding an $\varepsilon $ -approximate solution by the novel concept of $\varepsilon $ -essential feasibility. The underlying algorithmic approach is called successive incumbent transcending (SIT) algorithm and builds the foundation of our developed algorithm. A further highlight of this algorithm is that it inherently treats fractional objectives making the use of Dinkelbach's iterative algorithm obsolete. Numerical experiments show a speed-up of four orders of magnitude over state-of-the-art algorithms and almost three orders of magnitude of additional speed-up over Dinkelbach's algorithm for fractional programs. [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]

In a variety of fields, in particular those involving imaging and optics, we often measure signals whose phase is missing or has been irremediably distorted. Phase retrieval attempts to recover the phase information of a signal from the magnitude of its Fourier transform to enable the reconstruction of the original signal. Solving the phase retrieval problem is equivalent to recovering a signal from its auto-correlation function. In this paper, we assume the original signal to be sparse; this is a natural assumption in many applications, such as X-ray crystallography, speckle imaging and blind channel estimation. We propose an algorithm that resolves the phase retrieval problem in three stages, first, we leverage the finite rate of innovation sampling theory to super-resolve the auto-correlation function from a limited number of samples, second, we design a greedy algorithm that identifies the locations of a sparse solution given the super-resolved auto-correlation function, finally, we recover the amplitudes of the atoms given their locations and the measured auto-correlation function. Unlike traditional approaches that recover a discrete approximation of the underlying signal, our algorithm estimates the signal on a continuous domain, which makes it the first of its kind. Along with the algorithm, we derive its performance bound with a theoretical analysis and propose a set of enhancements to improve its computational complexity and noise resilience. Finally, we demonstrate the benefits of the proposed method via a comparison against Charge Flipping, a notable algorithm in crystallography. [ABSTRACT FROM AUTHOR]

Group testing is the problem of identifying $K$ defective items among $n$ items by pooling groups of items. In this paper, we design group testing algorithms for approximate recovery with order-optimal sample complexity by leveraging design and analysis tools from modern sparse-graph coding theory. Our algorithm, SAFFRON, recovers at least $(1-\varepsilon)K$ defective items w.p. $1-K/n^r$ with $m=2(1+r)C(\varepsilon)K\log _2{n}$ tests, where $\varepsilon$ is an arbitrarily small constant, $C(\varepsilon)$ is a precisely characterizable constant, and $r$ is any positive integer. The decoding complexity is $\Theta (K\log n)$. We also propose variations of SAFFRON, which are robust to noise and unknown offsets. For example, for $n \simeq 4.3\times 10^9$ and $K = 128$ , our algorithm is observed to recover all defective items with $m \simeq 8.3\times 10^{5}$ tests, even in the presence of noisy test results. Moreover, the decoding time takes less than 4 seconds on a laptop with a 2 GHz Intel Core i7 and 8 GB memory. [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]

In this paper, we study blind channel-and-signal estimation by exploiting the burst-sparse structure of angular-domain propagation channels in massive MIMO systems. The state-of-the-art approach utilizes the structured channel sparsity by sampling the angular-domain channel representation with a uniform angle-sampling grid, a.k.a. virtual channel representation. However, this approach is only applicable to uniform linear arrays and may cause a substantial performance loss due to the mismatch between the virtual representation and the true angle information. To tackle these challenges, we propose a sparse channel representation with a super-resolution sampling grid and a hidden Markovian support. Based on this, we develop a novel approximate inference based blind estimation algorithm to estimate the channel and the user signals simultaneously, with emphasis on the adoption of the expectation-maximization method to learn the angle information. Furthermore, we demonstrate the low-complexity implementation of our algorithm, making use of factor graph and message passing principles to compute the marginal posteriors. Numerical results show that our proposed method significantly reduces the estimation error compared to the state-of-the-art approach under various settings, which verifies the efficiency and robustness of our method. [ABSTRACT FROM AUTHOR]

In sketched clustering, a dataset of $T$ samples is first sketched down to a vector of modest size, from which the centroids are subsequently extracted. Its advantages include 1) reduced storage complexity and 2) centroid extraction complexity independent of $T$. For the sketching methodology recently proposed by Keriven et al., which can be interpreted as a random sampling of the empirical characteristic function, we propose a sketched clustering algorithm based on approximate message passing. Numerical experiments suggest that our approach is more efficient than the state-of-the-art sketched clustering algorithm “CL-OMPR” (in both computational and sample complexity) and more efficient than k-means++ when $T$ is large. [ABSTRACT FROM AUTHOR]

In this paper, we consider the (global and sum) energy efficiency optimization problem in downlink multi-input multi-output multi-cell systems, where all users suffer from multi-user interference. This is a challenging problem due to several reasons: First, it is a nonconvex fractional programming problem; second, the transmission rate functions are characterized by (complex-valued) transmit covariance matrices; and third the processing-related power consumption may depend on the transmission rate. We tackle this problem by the successive pseudoconvex approximation approach, and we argue that pseudoconvex optimization plays a fundamental role in designing novel iterative algorithms, not only because every locally optimal point of a pseudoconvex optimization problem is also globally optimal but also because a descent direction is easily obtained from every optimal point of a pseudoconvex optimization problem. The proposed algorithms have the following advantages: First, fast convergence as the structure of the original optimization problem is preserved as much as possible in the approximate problem solved in each iteration; second, easy implementation as each approximate problem is suitable for parallel computation and its solution has a closed-form expression; and third, guaranteed convergence to a stationary point or a Karush–Kuhn–Tucker point. The advantages of the proposed algorithm are also illustrated numerically. [ABSTRACT FROM AUTHOR]

Compared with the Fourier analysis, the fractional Fourier analysis is more suitable to process linear frequency modulation type non-stationary functions. To the best of our knowledge, the theoretical framework of the fractional Fourier analysis has not well established yet, especially for the fractional Fourier series (FrFS) and the discrete fractional Fourier transform (DFrFT) algorithms. To tackle with these problems, the efficient FrFS and DFrFT algorithms based on the Möbius function are proposed. First, the existence and applicability of the FrFS are analyzed basing on the Möbius inversion formula. Second, two kinds of fast algorithms for the infinite/finite FrFS are proposed. Then, based on the amplitude scaling relationship between the FrFS and samples of the FrFT, two efficient DFrFT algorithms are obtained, which are noted as the arithmetic discrete fractional Fourier transform (ADFrFT)-I and the ADFrFT-II. Importantly, the multiplication complexity of the two proposed ADFrFT algorithms is reduced to $O(M)$ , which is less than that of the state-of-the-art DFrFT algorithms. The parallel butterfly structure of the ADFrFT-II algorithm is suitable for the very large scale integration implementation. Finally, the simulations justify the efficiency of the ADFrFT algorithms in filtering and parameter evaluation of radar and optical signals. [ABSTRACT FROM AUTHOR]

This paper introduces an efficient algorithm for finding the dominant generalized eigenvectors of a pair of symmetric matrices. Combining tools from approximation theory and convex optimization, we develop a simple scalable algorithm with strong theoretical performance guarantees. More precisely, the algorithm retains the simplicity of the well-known power method but enjoys the asymptotic iteration complexity of the powerful Lanczos method. Unlike these classic techniques, our algorithm is designed to decompose the overall problem into a series of subproblems that only need to be solved approximately. The combination of good initializations, fast iterative solvers, and appropriate error control in solving the subproblems lead to a linear running time in the input sizes compared to the superlinear time for the traditional methods. The improved running time immediately offers acceleration for several applications. As an example, we demonstrate how the proposed algorithm can be used to accelerate canonical correlation analysis, which is a fundamental statistical tool for learning of a low-dimensional representation of high-dimensional objects. Numerical experiments on real-world datasets confirm that our approach yields significant improvements over the current state of the art. [ABSTRACT FROM AUTHOR]

This paper proposes a novel algorithm for target tracking with direction-of-arrival measurements, modeled by von Mises–Fisher distributions. The algorithm makes use of the assumed density framework with Gaussian distributions, in which the posterior probability density of the target state is approximated by a Gaussian density. A key component of this algorithm is that the proposed Bayesian model of the measurements takes into account the specific characteristics of angular measurements by using a von Mises–Fisher distribution. We propose two implementations of the algorithm, one based on first-order Taylor series expansion and another one based on sigma points. Simulation results show the benefits of the proposed algorithms in relation to other Gaussian filters in the literature. [ABSTRACT FROM AUTHOR]

In this paper, we devise a communication-efficient decentralized algorithm, named as communication-censored alternating direction method of multipliers (ADMM) (COCA), to solve a convex consensus optimization problem defined over a network. Similar to popular decentralized consensus optimization algorithms such as ADMM, at every iteration of COCA, a node exchanges its local variable with neighbors, and then updates its local variable according to the received neighboring variables and its local cost function. A different feature of COCA is that a node is not allowed to transmit its local variable to neighbors, if this variable is not sufficiently different to the previously transmitted one. The sufficiency of the difference is evaluated by a properly designed censoring function. Though this censoring strategy may slow down the optimization process, it effectively reduces the communication cost. We prove that when the censoring function is properly chosen, COCA converges to an optimal solution of the convex consensus optimization problem. Furthermore, if the local cost functions are strongly convex, COCA has a fast linear convergence rate. Numerical experiments demonstrate that, given a target solution accuracy, COCA is able to significantly reduce the overall communication cost compared to existing algorithms including ADMM, and hence fits for applications where network communication is a bottleneck. [ABSTRACT FROM AUTHOR]

Sequential state estimation in non-linear and non-Gaussian state spaces has a wide range of applications in statistics and signal processing. One of the most effective non-linear filtering approaches, particle filtering, suffers from weight degeneracy in high-dimensional filtering scenarios. Several avenues have been pursued to address high dimensionality. Among these, particle flow filters construct effective proposal distributions by using invertible flow to migrate particles continuously from the prior distribution to the posterior, and sequential Markov chain Monte Carlo (SMCMC) methods use a Metropolis–Hastings (MH) accept–reject approach to improve filtering performance. In this paper, we propose to combine the strengths of invertible particle flow and SMCMC by constructing a composite MH kernel within the SMCMC framework using invertible particle flow. In addition, we propose a Gaussian-mixture-model-based particle flow algorithm to construct effective MH kernels for multi-modal distributions. Simulation results show that for high-dimensional state estimation example problems, the proposed kernels significantly increase the acceptance rate with minimal additional computational overhead and improve estimation accuracy compared with state-of-the-art filtering algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we investigate hybrid analog/digital beamforming for multiple-input multiple-output (MIMO) systems with low-resolution analog-to-digital converters for millimeter wave (mmWave) communications. In the receiver, we propose to split the analog combining subsystem into a channel gain aggregation stage followed by a spreading stage. Both stages use phase shifters. Our goal is to design the two-stage analog combiner to optimize mutual information (MI) between the transmitted and quantized signals by effectively managing quantization error. To this end, we formulate an unconstrained MI maximization problem without a constant modulus constraint on analog combiners, and derive a two-stage analog combining solution. The solution achieves the optimal scaling law with respect to the number of radio frequency chains and maximizes the MI for homogeneous singular values of a MIMO channel. We further develop a two-stage analog combining algorithm to implement the derived solution for mmWave channels. By decoupling channel gain aggregation and spreading functions from the derived solution, the proposed algorithm implements the two functions by using array response vectors and a discrete Fourier transform matrix under the constant modulus constraint on each matrix element. Therefore, the proposed algorithm provides a near-optimal solution for the unconstrained problem, whereas conventional hybrid approaches offer a near optimal solution only for a constrained problem. The closed-form approximation of the ergodic rate is derived for the algorithm, showing that a practical digital combiner with two-stage analog combining also achieves the optimal scaling law. Simulation results validate the algorithm performance and the derived ergodic rate. [ABSTRACT FROM AUTHOR]

The problem of universal outlying sequence detection is studied, where the goal is to detect outlying sequences among $M$ sequences of samples. A sequence is considered as outlying if the observations therein are generated by a distribution different from those generating the observations in the majority of the sequences. In the universal setting, we are interested in identifying all the outlying sequences without knowing the underlying generating distributions. We consider the outlying sequence detection problem in three different scenarios: first, known number of outlying sequences; second, unknown number of identical outlying sequences; and finally, typical and outlying distributions forming clusters. In this paper, a class of tests based on distribution clustering is proposed. These tests are shown to be exponentially consistent with linear time complexity in $M$. Numerical results demonstrate that our clustering-based tests achieve similar performance to existing tests, while being considerably more computationally efficient. [ABSTRACT FROM AUTHOR]

The autoregressive (AR) model is a widely used model to understand time series data. Traditionally, the innovation noise of the AR is modeled as Gaussian. However, many time series applications, for example, financial time series data, are non-Gaussian, therefore, the AR model with more general heavy-tailed innovations is preferred. Another issue that frequently occurs in time series is missing values due to system data record failure or unexpected data loss. Although there are numerous works about Gaussian AR time series with missing values, as far as we know, there does not exist any work addressing the issue of missing data for the heavy-tailed AR model. In this paper, we consider this issue for the first time, and propose an efficient framework for parameter estimation from incomplete heavy-tailed time series based on a stochastic approximation expectation maximization coupled with a Markov Chain Monte Carlo procedure. The proposed algorithm is computationally cheap and easy to implement. The convergence of the proposed algorithm to a stationary point of the observed data likelihood is rigorously proved. Extensive simulations and real datasets analyses demonstrate the efficacy of the proposed framework. [ABSTRACT FROM AUTHOR]

Approximate message passing (AMP) methods have gained recent traction in sparse signal recovery. Additional information about the signal, or side information (SI), is commonly available and can aid in efficient signal recovery. This paper presents an AMP-based framework that exploits SI and can be readily implemented in various settings for which the SI results in separable distributions. To illustrate the simplicity and applicability of our approach, this framework is applied to a Bernoulli–Gaussian (BG) model and a time-varying birth-death-drift (BDD) signal model, motivated by applications in channel estimation. We develop a suite of algorithms, called AMP-SI, and derive denoisers for the BDD and BG models. Numerical evidence demonstrating the advantages of our approach are presented alongside empirical evidence of the accuracy of a proposed state evolution. [ABSTRACT FROM AUTHOR]

The optimal mean-reverting portfolio (MRP) design problem is an important task for statistical arbitrage, also known as pairs trading, in the financial markets. The target of the problem is to construct a portfolio of the underlying assets (possibly with an asset selection target) that can exhibit a satisfactory mean reversion property and a desirable variance property. In this paper, the optimal MRP design problem is studied under an investment leverage constraint representing the total investment positions on the underlying assets. A general problem formulation is proposed by considering the design targets subject to a leverage constraint. To solve the problem, a unified optimization framework based on the successive convex approximation method is developed. The superior performance of the proposed formulation and the algorithms are verified through numerical simulations on both synthetic data and real market data. [ABSTRACT FROM AUTHOR]

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

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

We generalize the 1-bit matrix completion problem to higher order tensors. Consider a rank- $r$ order- $d$ tensor $T$ in $\mathbb {R}^{N} \times \cdots \times \mathbb {R}^{N}$ with bounded entries. We show that when $r=O(1)$ , such a tensor can be estimated efficiently from only $m=O_r(Nd)$ binary measurements. This shows that the sample complexity of recovering a low-rank tensor from 1-bit measurements of a subset of its entries is roughly the same as recovering it from unquantized measurements—a result that had been known only in the matrix case, i.e., when $d=2$. By using a certain atomic M-norm as a convex proxy for rank, we allow for approximately low-rank tensors and give error bounds based on the M-norm of the tensor. We prove that the theoretical bounds are optimal both in the M-norm bound and the size $N$. Moreover, we show the advantage of directly using the low-rank tensor structure, rather than matricization, both theoretically and numerically. Specifically, we show how the 1-bit measurement model can be used for context-aware recommender systems. [ABSTRACT FROM AUTHOR]

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