基于最大范数的低秩稀疏分解模型

王斯琪; 冯象初; 张瑞; 李小平

doi:10.11999/JEIT150468

基于最大范数的低秩稀疏分解模型

doi: 10.11999/JEIT150468

基金项目:

国家自然科学基金(61271294, 61472303)和中央高校基本科研业务费专项资金(NSIY21)

计量
- 文章访问数: 1697
- HTML全文浏览量: 164
- PDF下载量: 1302
- 被引次数: 0
出版历程
- 收稿日期: 2015-04-22
- 修回日期: 2015-07-08
- 刊出日期: 2015-11-19

Low-rank Sparse Decomposition Model Based on Max-norm

Funds:

The National Natural Science Foundation of China (61271294, 61472303)

摘要

摘要: 为了更好地解决高维数据矩阵低秩稀疏分解问题，该文提出以Max-范数凸化秩函数的Max极小化模型，并给出该模型的相应算法。在对新模型计算复杂性分析的基础上，该文进一步提出了Max约束模型，改进模型不仅在分解问题中效果良好，且相应的投影梯度算法具有更强的时效性。实验结果表明，该文提出的两组模型对于低秩稀疏分解问题均行之有效。
- 图像分解 /
- Max-范数 /
- 投影梯度法
Abstract: In order to better solve the low-rank and sparse decomposition problem for high-dimensional data matrix, this paper puts forward a novel Max minimization model with Max-norm as the convex relaxation of the rank function, and provides the corresponding algorithm. Based on the complexity analysis on the novel model, an improved Max constraint model is further proposed, which not only has good performance in the decomposition problem but also can be solved with a fast projection gradient method. The experimental results show that the proposed two models are effective for low-rank sparse decomposition problem.
- Image decomposition /
- Max-norm /
- Projected Gradient Method (PGM)

HTML全文

参考文献(27)

Candes E J, Li Xiao-dong, Ma Yi, et al.. Robust principal component analysis?[J]. Journal of the ACM, 2011, 58(3): 11.

Candes E J and Plan Y. Matrix completion with noise[J]. Proceedings of the IEEE, 2010, 98(6): 925-936.

Chen Chong-yu, Cai Jian-fei, Lin Wei-si, et al.. Incremental low-rank and sparse decomposition for compressing videos captured by fixed cameras[J]. Journal of Visual Communication and Image Representation, 2015, 26(1): 338-348.

Sheng Bi-yun, Yang Wan-kou, Zhang Bao-chang, et al.. A non-negative low rank and sparse model for action recognition [C]. Proceedings of the 6th Chinese Conference on Pattern Recognition, Changsha, China, 2014: 266-275.

Li Sheng, Li Liang-yue, and Fu Yun. Low-Rank and Sparse Dictionary Learning[M]. Switzerland: Springer International Publishing, 2014: 61-85.

霍雷刚, 冯象初. 基于主成分分析和字典学习的高光谱遥感图像去噪方法[J]. 电子与信息学报, 2014, 36(11): 2723-2729.

Huo Lei-gang and Feng Xiang-chu. Denoising of hyperspectral remote sensing image based on principal component analysis and dictionary learning[J].? Journal of Electronics Information Technology, 2014, 36(11): 2723-2729.

张文娟, 冯象初. 非凸低秩稀疏约束的图像超像素分割方法[J]. 西安电子科技大学学报, 2013, 40(5): 86-91.

Zhang Wen-juan and Feng Xiang-chu. Image super-pixels segmentation method based on the non-convex low-rank and sparse constraints[J]. Journal of Xidian University, 2013, 40(5): 86-91.

Fazel M. Matrix rank minimization with applications[D]. [Ph.D. dissertation], Stanford University, 2002.

Srebro N and Shraibman A. Rank, Trace-norm and Max-norm [M]. Heidelberg: Springer Berlin Heidelberg, 2005: 545-560.

Cai T and Zhou Wen-xin. A max-norm constrained minimization approach to 1-bit matrix completion[J]. The Journal of Machine Learning Research, 2013, 14(1): 3619-3647.

Neyshabur B, Makarychev Y, and Srebro N. Clustering, hamming embedding, generalized lsh and the max norm [C]. Proceedings of the 25th International Conference on Algorithmic Learning Theory, Bled, 2014: 306-320.

Forster J, Schmitt N, Simon H U, et al.. Estimating the optimal margins of embeddings in euclidean half spaces[J]. Machine Learning, 2003, 51(3): 263-281.

庄哲民, 章聪友, 杨金耀, 等. 基于灰度特征和自适应阈值的虚拟背景提取研究[J]. 电子与信息学报, 2015, 37(2): 346-352.

Zhuang Zhe-min, Zhang Cong-you, Yang Jin-yao, et al.. Investigation on visual background extractor based on gray feature and adaptive threshold[J]. Journal of Electronics Information Technology, 2015, 37(2): 346-352.

张超, 吴小培, 吕钊. 基于独立分量分析的运动目标检测算法中对通道数选择和观测向量生成方式的实验和分析[J]. 电子与信息学报, 2015, 37(1): 137-142.

Zhang Chao, Wu Xiao-pei, and L Zhao. Experiments and analysis on observation vector generation and channel number selection in motion detection algorithm based on independent component analysis[J]. Journal of Electronics Information Technology, 2015, 37(1): 137-142.

Salakhutdinov R and Srebro N. Collaborative filtering in a non-uniform world: learning with the weighted trace norm[C]. Electronic Proceedings of the Neural Information Processing Systems Conference, Vancouver, 2010: 2056-2064.

Lee J, Recht B, Salakhutdinov R, et al.. Practical large-scale optimization for max-norm regularization[C]. Electronic Proceedings of the Neural Information Processing Systems Conference, Vancouver, 2010: 1297-1305.

Shen Jie, Xu Huan, and Li Ping. Online optimization for max-norm regularization[C]. Electronic Proceedings of the Neural Information Processing Systems Conference, Montreal, 2014: 1718-1726.

Linial N, Mendelson S, Schechtman G, et al.. Complexity measures of sign matrices[J]. Combinatorica, 2007, 27(4): 439-463.

Boyd S, Parikh N, Chu E, et al.. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine Learning, 2011, 3(1): 1-122.

Shen Yuan, Wen Zai-wen, and Zhang Yin. Augmented lagrangian alternating direction method for matrix separation based on low-rank factorization[J]. Optimization Methods and Software, 2014, 29(2): 239-263.

Hale E T, Yin Wo-tao, and Zhang Yin. Fixed-point continuation for Methodology and convergence[J]. SIAM Journal on Optimization, 2008, 19(3): 1107-1130.

Lin Chih-jen. Projected gradient methods for nonnegative matrix factorization[J]. Neural Computation, 2007, 19(10): 2756-2779.

Daubechies I, Fornasier M, and Loris I. Accelerated projected gradient method for linear inverse problems with sparsity constraints[J]. Journal of Fourier Analysis and Applications, 2008, 14(5/6): 764-792.

施引文献

资源附件(0)

访问统计