Ridge-Adding Homotopy Approach for l1-norm Minimization Problems
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E103-D No.6 pp.1380-1387
- Publication Date
- 2020/06/01
- Publicized
- 2020/03/10
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2019EDP7277
- Type of Manuscript
- PAPER
- Category
- Artificial Intelligence, Data Mining
Authors
Haoran LI
Jiangsu University
Binyu WANG
Jiangsu University
Jisheng DAI
Jiangsu University
Tianhong PAN
Jiangsu University,Anhui University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Haoran LI, Binyu WANG, Jisheng DAI, Tianhong PAN, "Ridge-Adding Homotopy Approach for l1-norm Minimization Problems" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 6, pp. 1380-1387, June 2020, doi: 10.1587/transinf.2019EDP7277.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019EDP7277/_p
Copy
@ARTICLE{e103-d_6_1380,
author={Haoran LI, Binyu WANG, Jisheng DAI, Tianhong PAN, },
journal={IEICE TRANSACTIONS on Information},
title={Ridge-Adding Homotopy Approach for l1-norm Minimization Problems},
year={2020},
volume={E103-D},
number={6},
pages={1380-1387},
abstract={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.},
keywords={},
doi={10.1587/transinf.2019EDP7277},
ISSN={1745-1361},
month={June},}
Copy
TY - JOUR
TI - Ridge-Adding Homotopy Approach for l1-norm Minimization Problems
T2 - IEICE TRANSACTIONS on Information
SP - 1380
EP - 1387
AU - Haoran LI
AU - Binyu WANG
AU - Jisheng DAI
AU - Tianhong PAN
PY - 2020
DO - 10.1587/transinf.2019EDP7277
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2020
AB - 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.
ER -
English
