Search

This paper introduces the stochastic Fejér-monotone hybrid steepest descent method (S-FM-HSDM) to solve affinely constrained and composite convex minimization tasks. The minimization task is not known exactly; noise contaminates the information about the composite loss function and the affine constraints. S-FM-HSDM generates sequences of random variables that, under certain conditions and with respect to a probability space, converge point-wise to solutions of the noiseless minimization task. S-FM-HSDM enjoys desirable attributes of optimization techniques such as splitting of variables and constant step size (learning rate). Furthermore, it provides a novel way of exploiting the information about the affine constraints via fixed-point sets of appropriate nonexpansive mappings. Among the offsprings of S-FM-HSDM, the hierarchical recursive least squares (HRLS) takes advantage of S-FM-HSDM's versatility toward affine constraints and offers a novel twist to LS by generating sequences of estimates that converge to solutions of a hierarchical optimization task: minimize a convex loss over the set of minimizers of the ensemble LS loss. Numerical tests on a sparsity-aware LS task show that HRLS compares favorably to several state-of-the-art convex, as well as non-convex, stochastic-approximation, and online-learning counterparts. [ABSTRACT FROM AUTHOR]

The universality of underdetermined systems has nurtured a variety of novel compressed sensing (CS) algorithms that ingeniously exploit data sparsity. Whereas well-studied greedy and iterative threshold-based CS recursions take the form of an adaptive filter followed by a proximal operator, this is no different in spirit from the role of block iterative equalizers, where structure is roughly exploited by the signal constellation slicer. By capitalizing on the intrinsic sparsity of signal modulations, we approach the concept of interblock interference (IBI) more proficiently in light of CS concepts, where the optimal feedback of detected symbols is devised adaptively. This should be contrasted with standard forms of IBI estimation/cancellation commonly seen in blockDFEs, where detection is restricted to a contiguous set of entries within the transmitted vector. A significant consequence of the latter is that, while block transceivers commonly employ some form of redundancy that accounts for IBI, a CS algorithm applied to the same transmitted vector may require no redundancy whatsoever, and is capable of retrieving both target symbol and IBI altogether. The CS-based iterative DFE acts as a more efficient re-estimation procedure, proposed under recursive-least-squares based adaptations. Besides maximizing system throughput, the new algorithms exhibit significantly higher performance when compared to existingmethods that focus solely on minimized redundancy. Simulations in several scenarios illustrate the merits of the unified approaches. [ABSTRACT FROM AUTHOR]

Techniques for hypothesis testing can be used to solve a broad class of nonstationarity detection problems, which is a key issue in a variety of applications. To achieve lower complexity and to deal with real-time detection in practical applications, we develop a new adaptive nonstationarity detector by exploiting a parametric model. A weighted maximum a posteriori (MAP) estimator is developed to estimate the parameters associated with the parametric model. We then derive a regularized Wald test from the weighted MAP estimate, which is adaptively implemented by a regularized recursive least squares (RLS) algorithm. Several important issues are discussed, including model order selection, forgetting factor and regularization parameter selection for RLS, and numerically stable implementation using QR decomposition, which are intrinsic parts of the proposed parametric adaptive detector. Simulation results are presented to illustrate the efficiency of the proposed nonstationarity detector, with adaptive estimation and automatic model selection, especially for “slowly varying” type of nonstationarity such as time-varying spectrums and speeches. [ABSTRACT FROM PUBLISHER]

We introduce a recursive adaptive group lasso algorithm for real-time penalized least squares prediction that produces a time sequence of optimal sparse predictor coefficient vectors. At each time index the proposed algorithm computes an exact update of the optimal ℓ1,∞-penalized recursive least squares (RLS) predictor. Each update minimizes a convex but nondifferentiable function optimization problem. We develop an on-line homotopy method to reduce the computational complexity. Numerical simulations demonstrate that the proposed algorithm outperforms the ℓ1 regularized RLS algorithm for a group sparse system identification problem and has lower implementation complexity than direct group lasso solvers. [ABSTRACT FROM PUBLISHER]

Using the ℓ1-norm to regularize the least-squares criterion, the batch least-absolute shrinkage and selection operator (Lasso) has well-documented merits for estimating sparse signals of interest emerging in various applications where observations adhere to parsimonious linear regression models. To cope with high complexity, increasing memory requirements, and lack of tracking capability that batch Lasso estimators face when processing observations sequentially, the present paper develops a novel time-weighted Lasso (TWL) approach. Performance analysis reveals that TWL cannot estimate consistently the desired signal support without compromising rate of convergence. This motivates the development of a time- and norm-weighted Lasso (TNWL) scheme with ℓ1-norm weights obtained from the recursive least-squares (RLS) algorithm. The resultant algorithm consistently estimates the support of sparse signals without reducing the convergence rate. To cope with sparsity-aware recursive real-time processing, novel adaptive algorithms are also developed to enable online coordinate descent solvers of TWL and TNWL that provably converge to the true sparse signal in the time-invariant case. Simulated tests compare competing alternatives and corroborate the performance of the novel algorithms in estimating time-invariant signals, and tracking time-varying signals under sparsity constraints. [ABSTRACT FROM AUTHOR]

In this paper, we derive low-complexity recursive least squares (RLS) adaptive filtering algorithms. We express the RLS problem in terms of auxiliary normal equations with respect to increments of the filter weights and apply this approach to the exponentially weighted and sliding window cases to derive new RLS techniques. For solving the auxiliary equations, line search methods are used. We first consider conjugate gradient iterations with a complexity of O(N²) operations per sample; N being the number of the filter weights. To reduce the complexity and make the algorithms more suitable for finite precision implementation, we propose a new dichotomous coordinate descent (DCD) algorithm and apply it to the auxiliary equations. This results in a transversal RLS adaptive filter with complexity as low as 3N multiplications per sample, which is only slightly higher than the complexity of the least mean squares (LMS) algorithm (2N multiplications). Simulations are used to compare the performance of the proposed algorithms against the classical RLS and known advanced adaptive algorithms. Fixed-point FPGA implementation of the proposed DCD-based RLS algorithm is also discussed and results of such implementation are presented. [ABSTRACT FROM AUTHOR]

A computationally reduced version of the fast H∞, filter (FHF) is derived under the assumption that the input signal to the unknown system can be represented by an autoregressive (AR) model whose order M is much lower than the filter length N. The resulting filter, referred to as the predictor-based fast H∞ filter (P-FHF), has a computational requirement of 3N + O(M) multiplications per iteration, which is considerably lower than the requirement for the FHF if M is sufficiently smaller than N. The validity of the P-FHF are confirmed by computer simulations. [ABSTRACT FROM AUTHOR]

In this paper, a new control mechanism for the vari- able forgetting factor (VFF) of the recursive least square (RLS) adaptive algorithm is presented. The control algorithm is basically a gradient-based method of which the gradient is derived from an improved mean square error analysis of RLS. The new mean square error analysis exploits the correlation of the inverse of the correlation matrix with itself that yields improved theoretical results, especially in the transient and steady-state mean square error. It is shown that the theoretical analysis is close to simulation results for different forgetting factors and different model orders. The analysis yields a dynamic equation of mean square error that can be used to derive a dynamic equation of the gradient of mean square error to control the forgetting factor. The dynamic equation can produce a positive gradient when the error is large and a negative gradient when the error is in the steady state. Compared with other variable forgetting factor algorithms, the new control algorithm gives fast tracking and small mean square model error for different signal-to-noise ratios (SNRs). [ABSTRACT FROM AUTHOR]

In some estimation or identification techniques, a for- getting factor p has been used to improve the tracking performance for time-varying systems. However, the value of p has been typically determined empirically, without any evidence of optimality. In our previous work, this open problem is solved using the frame- work of H∞ optimization. The resultant H∞ filter enables the forgetting factor p to be optimized through a process noise that is determined by the filter Riccati equation. This paper seeks to further explain the previously derived H∞filter, giving an H∞ interpretation of its tracking capability. Additionally, a fast algorithm of the H∞ filter, called the fast H∞ filter, is presented when the observation matrix has a shifting property. Finally, the effectiveness of the derived fast algorithm is illustrated for time-variant system identification using several computer simulations. Here, the fast H∞, filter is shown to outperform the well known least-mean-square algorithm and the fast Kalman filter in convergence rate. [ABSTRACT FROM AUTHOR]

A new fast recursive least squares (RLS) algorithm is introduced. By making use of RLS interpolation as well as prediction, the algorithm generates the transversal filter weights without suffering the poor numerical attributes of the FTP algorithm. The Kalman gain vector is generated at each time step in terms of interpolation residuals. The interpolation residuals are calculated in an order recursive manner. For an Nth-order problem, the procedure requires O(N log[sub2] N) operations per iteration. This is achieved via a divide-and-conquer approach. Computer simulations suggest that the new algorithm is numerically robust, running successfully for many millions of iterations. [ABSTRACT FROM AUTHOR]