Ridge-Adding Homotopy Approach for l1-norm Minimization Problems

Haoran LI  Binyu WANG  Jisheng DAI  Tianhong PAN  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.6   pp.1380-1387
Publication Date: 2020/06/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019EDP7277
Type of Manuscript: PAPER
Category: Artificial Intelligence, Data Mining
Keyword: 
l1-norm minimization,  homotopy algorithm,  singularity,  support vector machine (SVM),  

Full Text: PDF>>
Buy this Article




Summary: 
Homotopy algorithm provides a very powerful approach to select the best regularization term for the l1-norm minimization problem, but it is lack of provision for handling singularities. The singularity problem might be frequently encountered in practical implementations if the measurement matrix contains duplicate columns, approximate columns or columns with linear dependent in kernel space. The existing method for handling Homotopy singularities introduces a high-dimensional random ridge term into the measurement matrix, which has at least two shortcomings: 1) it is very difficult to choose a proper ridge term that applies to several different measurement matrices; and 2) the high-dimensional ridge term may accumulatively degrade the recovery performance for large-scale applications. To get around these shortcomings, a modified ridge-adding method is proposed to deal with the singularity problem, which introduces a low-dimensional random ridge vector into the l1-norm minimization problem directly. Our method provides a much simpler implementation, and it can alleviate the degradation caused by the ridge term because the dimension of ridge term in the proposed method is much smaller than the original one. Moreover, the proposed method can be further extended to handle the SVMpath initialization singularities. Theoretical analysis and experimental results validate the performance of the proposed method.