For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Ridge-Adding Homotopy Approach for l1-norm Minimization Problems
Haoran LI Binyu WANG Jisheng DAI Tianhong PAN
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2020/06/01
Online ISSN: 1745-1361
Type of Manuscript: PAPER
Category: Artificial Intelligence, Data Mining
l1-norm minimization, homotopy algorithm, singularity, support vector machine (SVM),
Full Text: PDF>>
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.