Minimax Concave Penalty Regularized Adaptive System Identification

Bowen Li, Suya Wu, Erin E. Tripp, Ali Pezeshki, Vahid TarokharXiv 2022 · DOI · arXiv

Abstract: We develop a recursive least square (RLS) type algorithm with a minimax concave penalty (MCP) for adaptive identification of a sparse tap-weight vector that represents a communication channel. The proposed algorithm recursively yields its estimate of the tap-vector, from noisy streaming observations of a received signal, using expectation-maximization (EM) update. We prove the convergence of our algorithm to a local optimum and provide bounds for the steady state error. Using simulation studies of Rayleigh fading channel, Volterra system and multivariate time series model, we demonstrate that our algorithm outperforms, in the mean-squared error (MSE) sense, the standard RLS and the $\ell_1$-regularized RLS.

Introduction

Adaptive system identification is a cornerstone of signal processing, used to estimate the internal parameters of systems—such as communication channels or echo paths—from streaming input-output data. In many practical applications, these systems are "sparse," meaning only a small subset of the potential parameters are non-zero. While the standard Recursive Least Squares (RLS) algorithm is effective for tracking time-varying systems, it does not exploit this sparsity.

To address this, researchers have previously employed $\ell_1$-regularization (the Lasso). However, the $\ell_1$ penalty introduces a "shrinkage bias," where the magnitudes of large, active weights are systematically underestimated. This paper proposes a new algorithm, SPARLS-MCP, which utilizes the non-convex Minimax Concave Penalty (MCP) to achieve sparse estimation without the associated bias.

Methodology: MCP and the EM Framework

The core of the proposed approach is the use of the Minimax Concave Penalty (MCP). Unlike the $\ell_1$ penalty, which increases linearly with the magnitude of the weight, the MCP "levels off" once a weight exceeds a certain threshold. This allows the algorithm to aggressively suppress noise (keeping small weights at zero) while preserving the integrity of significant signals.

Comparison of the MCP penalty function for various alpha values against the standard L1 penalty.

To solve the resulting non-convex optimization problem in an online setting, the authors leverage an Expectation-Maximization (EM) framework. By treating the true signal as latent data, the EM update decomposes the complex global problem into a series of simpler "firm thresholding" operations. This leads to the development of the SPARLS-MCP algorithm, a recursive version of the Sparse Adaptive Least Squares (SPALS) method that updates estimates incrementally as new data arrives.

Experimental Results

The performance of SPARLS-MCP was evaluated across several simulated environments, including Rayleigh fading channels (Jake’s model), non-linear Volterra systems, and multivariate time series forecasting.

In all scenarios, SPARLS-MCP demonstrated superior performance compared to both standard RLS and the Lasso-based SPARLS-$\ell_1$. As shown in the tracking performance plots, the MCP-based approach achieves lower Normalized Mean Squared Error (NMSE) and faster convergence.

NMSE performance comparison of RLS, SPARLS-L1, and SPARLS-MCP under different SNR conditions.

Key findings include:

  • Tracking Accuracy: In Jake's model, SPARLS-MCP provided an additional 2dB gain over the Lasso-based version.
  • Robustness to Noise: The performance advantage was even more significant in Volterra systems, ranging from 2dB to 5dB, particularly at higher Signal-to-Noise Ratios (SNR).
  • Forecasting: For multivariate time series, the MCP approach reduced mean prediction error by approximately 67% compared to Group Lasso methods.

Conclusion

The SPARLS-MCP algorithm effectively bridges the gap between the computationally efficient but biased $\ell_1$ penalty and the unbiased but NP-hard $\ell_0$ penalty. By utilizing an EM-based recursive update, it provides a robust solution for real-time sparse system identification. Future work will focus on providing a formal convergence proof for the recursive implementation and extending the framework to other non-convex recovery techniques.

Summary updated

Abstract

We develop a recursive least square (RLS) type algorithm with a minimax concave penalty (MCP) for adaptive identification of a sparse tap-weight vector that represents a communication channel. The proposed algorithm recursively yields its estimate of the tap-vector, from noisy streaming observations of a received signal, using expectation-maximization (EM) update. We prove the convergence of our algorithm to a local optimum and provide bounds for the steady state error. Using simulation studies of Rayleigh fading channel, Volterra system and multivariate time series model, we demonstrate that our algorithm outperforms, in the mean-squared error (MSE) sense, the standard RLS and the $\ell_1$-regularized RLS.
BibTeX
@misc{li2022minimax,
  author = {Bowen Li and Suya Wu and Erin E. Tripp and Ali Pezeshki and Vahid Tarokh},
  title = {{Minimax Concave Penalty Regularized Adaptive System Identification}},
  year = {2022},
  eprint = {2211.03903},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2211.03903},
}
Figure