Theory and Algorithms for Solving the Multivariate Linear Model With a Unified Framework: From ℓ1-Norm Approximation to ℓ1-Norm Optimization
Abstract
It is a challenging problem to solve the multivariate linear model (MLM) <inline-formula> <tex-math notation="LaTeX">$\|\mathbf {Ax}= \mathbf {b}\|$ </tex-math></inline-formula> with the <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-norm approximation method such that <inline-formula> <tex-math notation="LaTeX">$\|\mathbf {Ax}-\mathbf {b}\|_{1}$ </tex-math></inline-formula>, the <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-norm of the residual error vector (REV), is minimized. In this work, our contributions lie in three aspects: firstly, a REV-based equivalence theorem for the structure of the <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-norm optimal solution to the MLM is proposed and proved, which establishes a theoretical connection between MLM <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-norm approximation and residual-domain basis-pursuit-type <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-optimization, with the MLM solution reconstructed through the Moore–Penrose inverse; secondly, the REV formulation is extended to the weighted <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-norm approximation problem by using diagonal scaling of the residual vector; thirdly, a unified algorithmic framework for solving the MLM with <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-norm optimization is proposed and six REV-based algorithms (L1-GPSR, L1-TNIPM, L1-HP, L1-IST, L1-ADM, L1-POB) are designed, where established optimization techniques are reformulated under a common residual-domain model, input-output structure, and Moore–Penrose inverse reconstruction scheme. There are three significant characteristics in the algorithms discussed: they are implemented with simple matrix operations which do not depend on specific optimization solvers; they are described with algorithmic pseudo-codes and implemented with Python and Octave/MATLAB which means easy usage; and the high accuracy and efficiency of our six REV-based algorithms can be achieved successfully in the scenarios with different levels of data redundancy. Numerical and real-data experiments further illustrate the accuracy, efficiency, and robustness of the proposed <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-based estimators, especially their reduced sensitivity to influential observations compared with the least-squares estimator. We hope that the unified theoretic and algorithmic framework with source code released on GitHub could motivate the applications of the <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-norm optimization for <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-based parameter estimation of MLM arising in science, technology, engineering, mathematics, economics, and so on.