WANG Caihua, LIU Juan, MIN Wenwen, QU Aiping. A Novel Sparse Penalty for Singular Value Decomposition[J]. Chinese Journal of Electronics, 2017, 26(2): 306-312. doi: 10.1049/cje.2017.01.025
Citation: WANG Caihua, LIU Juan, MIN Wenwen, QU Aiping. A Novel Sparse Penalty for Singular Value Decomposition[J]. Chinese Journal of Electronics, 2017, 26(2): 306-312. doi: 10.1049/cje.2017.01.025

A Novel Sparse Penalty for Singular Value Decomposition

doi: 10.1049/cje.2017.01.025
Funds:  This work is supported by the National Natural Science Foundation of China (No.61272274, No.60970063), the National Science Foundation of Jiangsu Province (No.BK20161249) and the program for New Century Excellent Talents in Universities (No.NCET-10-0644).
More Information
  • Corresponding author: LIU Juan (corresponding author) was born in Hubei Province, China, in 1970, she received the Ph.D degree in computer science from Wuhan University and now serves as a professor and Ph.D supervisor in Wuhan University. Her research interests include data mining, nature language process and bioinformatics. (Email:liujuan@whu.edu.cn)
  • Received Date: 2014-11-14
  • Rev Recd Date: 2015-05-26
  • Publish Date: 2017-03-10
  • Singular value decomposition (SVD) is a tool widely used in data denoising, matrix approximation, recommendation system, text mining and computer vision. A majority of applications prefer sparse singular vectors to capture inherent structures and patterns of the input data so that the results are interpretable. We present a novel penalty for SVD to achieve sparsity. Comparing with the traditional penalties, the proposed penalty is scale, dimensional insensitive and bounded between 0 and 1, which are in favor of controlling sparsity. Regulated by the penalty, we provide an efficient algorithm to project a vector onto a given sparse level in O(n) expected time. The efficient projection algorithm serve as a drudge for sparse SVD (SSVD). In experiments, SSVD is efficient and could capture the latent structures and patterns of the input data.
  • loading
  • O. Alter, P.O. Brown and D. Botstein, "Processing and modeling genome-wide expression data using singular value decomposition", Proc. Natl. Acad. Sci., Vol.97, No.18, pp.10101-10106, 2001.
    J.Z. Huang, H. Shen and A. Buja, "The analysis of two-way functional data using two-way regularized singular value decompositions", J. Am. Stat. Assoc., Vol.104, No.488, pp.1609-1620, 2009.
    H.S. Prasantha, H.L. Shashidhara and K.N.B. Murthy, "Image compression using SVD", Proceedings of the International Conference on Computational Intelligence and Multimedia Applications, pp.143-145, 2008.
    A. Thomasian, V. Castelli and C. Li, "Clustering and singular value decomposition for approximate indexing in high dimensional spaces", Proceedings of the Seventh International Conference on Information and Knowledge Management, pp.201-207, 1998.
    Yang, Dan, Zongming Ma and Andreas Buja, "A sparse SVD method for high-dimensional data", Journal of Computational and Graphical Statistics, Vol.23, No.4, pp.923-942, 2014.
    Michael W. Berry, Susan T. Dumais and Gavin W. O'Brien, "Using linear algebra for intelligent information retrieval", SIAM Rev, Vol.37, No.4, pp.573-595, 1995.
    Scott Deerwester, Susan T. Dumais, Thomas K. Landauer, George W. Furnas, and Richard A. Harshman, "Indexing by latent semantic analysis", J. Soc. Inf. Sci., Vol.41, No.6, pp.391-407, 1990.
    D.M. Witten, R. Tibshirani, and T. Hastie, "A penalized matrix decomposition", with applications to sparse principal components and canonical correlation analysis, Biostatistics, Vol.10, pp.515-534, 2009.
    Lee M, Shen H, Huang J Z, et al., "Biclustering via sparse singular value decomposition", Biometrics, Vol.66, No.4, pp.1087-1095, 2010.
    A. d'Aspremont, L. El Ghaoui, M.I. Jordan, G.R. Lanckriet, "A direct formulation for sparse PCA using semidefinite programming", Advances in Neural Information Processing Systems, Vol.49, No.3, pp.434-448, 2005.
    Deyu Meng, Hengbin Cui, Zongben Xu, Kaili Jing, "Following the entire solution path of sparse principal component analysis by coordinate-pairwise algorithm", Data & Knowledge Engineering, Vol.88, pp.25-36, 2013.
    Deyu Meng, Qian Zhao, Zongben Xu, "Improve robustness of sparse PCA by L1-norm maximization", Pattern Recognition, Vol.45, pp.487-497, 2012.
    Qian Zhao, Deyu Meng, Zongben Xu, "Robust sparse PCA", Science in China, Vol.57, pp.1-14, 2014.
    C.D. Sigg, J.M. Buhmann, "Expectation maximization for sparse and nonnegative PCA", International Conference on Machine Learning, ICML, pp.960-967, 2008.
    Lin Chih-Jen, "Projected gradient methods for nonnegative matrix factorization", Neural Computation, Vol.19, No.10, pp.2756-2779, 2007.
    W. Zheng, S.Z. Li, J.H. Lai, et al., "On constrained sparse matrix factorization", IEEE International Conference on Computer Vision, pp.1-8, 2007.
    F. Bach, J. Mairal and J. Ponce, "Convex sparse matrix factorizations", https://arxiv.org/abs/0812.1869, 2008.
    G.I. Allen, L. Grosenick and J. Taylor, "A generalized least squares matrix decomposition", Journal of the American Statistical Association, Vol.109, No.505, pp.145-159, 2014.
    R. Tibshirani, "Regression shrinkage and selection via the lasso", Journal of the Royal Statistical Society, Series B, Vol.58, pp.267-288, 1996.
    H. Zou, "The adaptive lasso and its oracle properties", Journal of the American Statistical Association, Vol.101, pp.1418-1429, 2006.
    H.H. Zhang and W. Lu, "Adaptive-lasso for Cox's proportional hazard model", Biometrika, Vol.94, pp.691-703, 2007.
    R. Tibshirani, M. Saunders and S. Rosset, "Sparsity and smoothness via the fused lasso", Journal of the Royal Statistical Society:Series B (Statistical Methodology), Vol.67, No.1, pp.91-108, 2005.
    J. Fan and R. Li, "Variable selection via nonconcave penalized likelihood and its oracle properties", Journal of the American Statistical Association, Vol.96, No.456, pp.1348-1360, 2001.
    H. Wang, R. Li, C.L. Tsai, "Tuning parameter selectors for the smoothly clipped absolute deviation method", Biometrika, Vol.94, No.3, pp.553-568, 2007.
    Y. Kim, H. Choi and H.S. Oh, "Smoothly clipped absolute deviation on high dimensions", Journal of the American Statistical Association, Vol.103, No.484, pp.1665-1673, 2008.
    John Duchi, Shai Shalev-Shwartz, Yoram Singer and Yoram Singer, "Efficient projections onto the l1-ball for learning in high dimensions", International Conference on Machine Learning, ICML, pp.272-279, 2008.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (151) PDF downloads(1142) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return