access icon openaccess Homotopy algorithm for l 1-norm minimisation problems

This is an open access article published by the IET under the Creative Commons Attribution-NonCommercial License
(http://creativecommons.org/licenses/by-nc/3.0/)
Received 25/08/2013, Accepted 01/05/2014, Revised 10/03/2014, Published 23/02/2015

This paper proposes a novel approach to handle the singularity problem in the Homotopy algorithm. Following a state-of-art ridge-adding-based method, the authors introduce a random ridge term to each element of the measure matrix to avoid the occurrence of singularities. Then, the authors give the sufficient condition of avoiding singularities, and prove that adding random ridge is greatly useful to deal with the singularity problem, even the random ridge tends to zero. Although the main procedures in the method coincide with the state-of-art method, all the derivations and theoretical analyses are different because of distinct forms of optimisation problems. Thus, this work is by no means a trivial task. Moreover, the authors note that the most computationally expensive step in the proposed method is the inversion of active matrices, whose time complexity relative to that of other required operations is proportional to the active set's cardinality. This motivates us to develop an efficient QR update algorithm based on the new ridge-adding-based method, which is incorporated in Givens QR factorisation and Gaussian elimination. It turns out that, with such new QR update algorithm, the previous ratio of time complexities can be reduced to a constant order. As a consequence, the new method can eliminate the bottleneck of matrix inversion in the improved Homotopy algorithm.

Inspec keywords: Gaussian processes; minimisation; matrix algebra

Other keywords: state-of-art ridge adding based method; active matrices; l1-norm minimisation problems; optimisation problems; homotopy algorithm; singularity problem; ridge adding based method; matrix inversion; matrix measurement; Gaussian elimination

Subjects: Algebra; Other topics in statistics; Other topics in statistics; Statistics; Algebra; Algebra; Optimisation techniques; Optimisation; Optimisation techniques

References

    1. 1)
    2. 2)
    3. 3)
    4. 4)
      • 13. Hastie, T., Rosset, S., Tibshirani, R., Zhu, J.: ‘The entire regularization path for the support vector machine’, J. Mach. Learn. Res., 2004, 5, pp. 1391–1415.
    5. 5)
    6. 6)
    7. 7)
    8. 8)
      • 2. Yang, A., Ganesh, A., Sastry, S., Ma, Y.: ‘Fast l1-minimization algorithms and an application in robust face recognition: A review’. Techical Report UCB/EECS-2010-13, EECS Department, University of California, Berkeley, February 2010.
    9. 9)
      • 18. Grant, M., Boyd, S.: ‘CVX: Matlab software for disciplined convex programming, version 1.21’, http://cvxr.com/cvx, September 2010.
    10. 10)
    11. 11)
      • 19. Grant, M., Boyd, S.: ‘Graph implementations for nonsmooth convex programs’, in Blondel, V., Boyd, S., Kimura, H. (Eds.): ‘Recent advances in learning and control’, ser. Lecture Notes in Control and Information Sciences, (Springer-Verlag Limited, 2008), pp. 95–110, ‘http://stanford.edu/boyd/graph_dcp.html’.
    12. 12)
    13. 13)
    14. 14)
    15. 15)
    16. 16)
      • 20. Frank, A., Asuncion, A.: ‘UCI machine learning repository’, 2010. [Online]. Available: http://archive.ics.uci.edu/ml.
    17. 17)
    18. 18)
      • 3. Tibshirani, R.: ‘Regression shrinkage and selection via the Lasso’, J. R. Stat. Soc., 1996, 58, pp. 267–288.
    19. 19)
    20. 20)
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-spr.2013.0338
Loading

Related content

content/journals/10.1049/iet-spr.2013.0338
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading