iccv iccv2013 iccv2013-292 iccv2013-292-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Mithun Das Gupta, Sanjeev Kumar
Abstract: In this paper, we investigate the properties of Lp norm (p ≤ 1) within a projection framework. We start with the (KpK T≤ equations of the neoctni-olnin efraarm optimization problem a thnde then use its key properties to arrive at an algorithm for Lp norm projection on the non-negative simplex. We compare with L1projection which needs prior knowledge of the true norm, as well as hard thresholding based sparsificationproposed in recent compressed sensing literature. We show performance improvements compared to these techniques across different vision applications.
[1] K. Bredies and D. A. Lorenz. Minimization of non-smooth, non-convex functionals by iterative thresholding, 2009. 5
[2] L. M. Bregman. The method of successive projection for finding a common point of convex sets. In Soviet Math. Dokl., volume 6, pages 688–692, 1965. 5
[3] P. Brucker, B. Jurisch, and B. Sievers. A branch and bound algorithm for the job-shop scheduling problem. Discrete Ap-
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14] plied Mathematics, 49(1-3): 107–127, 1994. 2 E. J. Candes and J. Romberg. Practical signal recovery from random projections. In Proc. SPIE Computational Imaging, volume 5674, pages 76–86, 2005. 5, 7 I. Daubechies, R. Devore, M. Fornasier, and C. S. Gntrk. Iteratively reweighted least squares minimization for sparse recovery. Comm. Pure Appl. Math, 2008. 1 D. Donoho and I. Johnstone. Ideal spatial adaptation via wavelet shrinkage. Biometrika, 81:425–455, 1994. 1 J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra. Efficient projections onto the l1-ball for learning in high dimensions. In ICML ’08, 2008. 2, 3 L. Gan. Block compressed sensing of natural images. In Proc. of Intl. Conf. Digital Signal Processing, pages 403– 406, 2007. 5 R. Garg and R. Khandekar. Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property. In ICML ’09, pages 337–344, 2009. 5 G. Gasso, A. Rakotomamonjy, and S. Canu. Recovering sparse signals with a certain family of nonconvex penalties and dc programming. IEEE Trans. Sig. Proc., 57(12):4686– 4698, Dec. 2009. 6 D. Geman and G. Reynolds. Constrained restoration and recovery of discontinuities. PAMI, 14(3):367–383, 1992. 5 D. Geman and C. Yang. Nonlinear image recovery with halfquadratic regularization. PAMI, 4(3):932–946, 1995. 5 M. D. Gupta, S. Kumar, and J. Xiao. L1projections with box constraints. CoRR, abs/1010.0141, 2010. 3 D. Krishnan and R. Fergus. Analytic hyper-laplacian priors for fast image deconvolution. In NIPS, 2009. 3, 7
[15] N. Naikal, A. Yang, and S. S. Sastry. Informative feature selection for object recognition via sparse pca. Technical Report UCB/EECS-201 1-27, EECS Dept., Univ. California, Berkeley, Apr 2011. 7, 8
[16] N. Naikal, A. Y. Yang, and S. S. Sastry. Towards an efficient distributed object recognition system in wireless. Information Fusion, 2010. 8
[17] D. Needell and J. A. Tropp. Cosamp: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis, 26(3):301–321, Apr 2008. 5
[18] J. Nocedal and S. J. Wright. Numerical Optimization. Springer, 2000. 3
[19] S. Rosset and J. Zhu. Piecewise linear regularized solution paths. Annals of Statistics, 35: 1012, 2007. 2
[20] R. Saab, R. Chartrand, and O. Yilmaz. Stable sparse approximations via nonconvex optimization. In Proc. 33rd Int. Conf. Accoustic Speech and Signal Processing, ICASSP, 2008. 6
[21] H. Su, A. W. Yu, and L. Fei-Fei. Efficient euclidean projections onto the intersection of norm balls. In International Conference on Machine Learning (ICML), Edinburgh, UK, June 2012. 3
[22] H. Tuy. Concave programming under linear constraints. Soviet Math, (5): 1437–1440, 1964. 2
[23] B. E. Usevich. A tutorial on modern lossy image compression: Foundations of JPEG 2000. IEEE Signal Processing Mag., pages 22–35, September 2001 . 1
[24] Y. Wang, J. Yang, W. Yin, , and Y. Zhang. A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imaging Sciences, 1(3):248–272, 2008. 5
[25] H. Zou, T. Hastie, and R. Tibshirani. Sparse Principal Com- ponent Analysis. J. Computational and Graphical Statistics, 15, 2004. 7 11660000