Convex low rank approximation. (English) Zbl 1398.68586
Summary: Low rank approximation is an important tool in many applications. Given an observed matrix with elements corrupted by Gaussian noise it is possible to find the best approximating matrix of a given rank through singular value decomposition. However, due to the non-convexity of the formulation it is not possible to incorporate any additional knowledge of the sought matrix without resorting to heuristic optimization techniques. In this paper we propose a convex formulation that is more flexible in that it can be combined with any other convex constraints and penalty functions. The formulation uses the so called convex envelope, which is the provably best possible convex relaxation. We show that for a general class of problems the envelope can be efficiently computed and may in some cases even have a closed form expression. We test the algorithm on a number of real and synthetic data sets and show state-of-the-art results.
MSC:
| 68T45 | Machine vision and scene understanding |
| 65F30 | Other matrix algorithms (MSC2010) |
References:
| [1] | Andersson, F; Carlsson, M; Tourneret, JY; Wendt, H, A new frequency estimation method for equally and unequally spaced data, IEEE Transactions on Signal Processing, 62, 5761-5774, (2014) · Zbl 1394.94042 · doi:10.1109/TSP.2014.2358961 |
| [2] | Angst, R., Zach, C., & Pollefeys, M. (2011). The generalized trace-norm and its application to structure-from-motion problems. In International Conference on Computer Vision |
| [3] | Aquiar, P. M. Q., Stosic, M., & Xavier, J. M. F. (2008). Spectrally optimal factorization of incomplete matrices. In IEEE Conference on Computer Vision and Pattern Recognition |
| [4] | Argyriou, A., Foygel, R., & Srebro, N. (2012). Sparse prediction with the k-support norm. In Advances in Neural Information Processing Systems |
| [5] | Basri, R; Jacobs, D; Kemelmacher, I, Photometric stereo with general, unknown lighting, International Journal of Computer Vision, 72, 239-257, (2007) · doi:10.1007/s11263-006-8815-7 |
| [6] | Boyd, S; Parikh, N; Chu, E; Peleato, B; Eckstein, J, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3, 1-122, (2011) · Zbl 1229.90122 · doi:10.1561/2200000016 |
| [7] | Bregler, C., Hertzmann, A., & Biermann, H. (2000). Recovering non-rigid 3d shape from image streams. In IEEE Conference on Computer Vision and Pattern Recognition |
| [8] | Buchanan, A.M., & Fitzgibbon, A.W. (2005). Damped newton algorithms for matrix factorization with missing data. In IEEE Conference on Computer Vision and Pattern Recognition |
| [9] | Cabral, R., de la Torre, F., Costeira, J., & Bernardino, A. (2013). Unifying nuclear norm and bilinear factorization approaches for low-rank matrix decomposition. In International Conference on Computer Vision |
| [10] | Cai, JF; Candès, EJ; Shen, Z, A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20, 1956-1982, (2010) · Zbl 1201.90155 · doi:10.1137/080738970 |
| [11] | Candès, EJ; Li, X; Ma, Y; Wright, J, Robust principal component analysis?, Journal of the ACM, 58, 11:1-11:37, (2011) · Zbl 1327.62369 · doi:10.1145/1970392.1970395 |
| [12] | Eckart, C; Young, G, The approximation of one matrix by another of lower rank, Psychometrika, 1, 211-218, (1936) · JFM 62.1075.02 · doi:10.1007/BF02288367 |
| [13] | Eriksson, A; Hengel, A, Efficient computation of robust weighted low-rank matrix approximations using the \(L_1\) norm, IEEE Transactions on Pattern Analysis and Machine Intelligence, 34, 1681-1690, (2012) · doi:10.1109/TPAMI.2012.116 |
| [14] | Eriksson, A., Thanh, P. T., Chin, T.J., & Reid, I. (2015). The k-support norm and convex envelopes of cardinality and rank. In The IEEE Conference on Computer Vision and Pattern Recognition |
| [15] | Favaro, P., Vidal, R., & Ravichandran, A. (2011). A closed form solution to robust subspace estimation and clustering. In IEEE Confernece on Computer Vision and Pattern Recognition |
| [16] | Fazel, M., Hindi, H., & Boyd, S. P. (2001). A rank minimization heuristic with application to minimum order system approximation. In American Control Conference |
| [17] | Garg, R., Roussos, A., & de Agapito, L. (2013). Dense variational reconstruction of non-rigid surfaces from monocular video. In IEEE Conference on Computer Vision and Pattern Recognition |
| [18] | Garg, R; Roussos, A; Agapito, L, A variational approach to video registration with subspace constraints, International Journal of Computer Vision, 104, 286-314, (2013) · Zbl 1304.68175 · doi:10.1007/s11263-012-0607-7 |
| [19] | Gillis, N; Glinuer, F, Low-rank matrix approximation with weights or missing data is NP-hard, SIAM Journal on Matrix Analysis and Applications, 32, 4, (2011) · Zbl 1242.65077 · doi:10.1137/110820361 |
| [20] | Hu, Y; Zhang, D; Ye, J; Li, X; He, X, Fast and accurate matrix completion via truncated nuclear norm regularization, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35, 2117-2130, (2013) · doi:10.1109/TPAMI.2012.271 |
| [21] | Jacobs, D. (1997). Linear fitting with missing data: Applications to structure-from-motion and to characterizing intensity images. In IEEE Conference on Computer Vision and Pattern Recognition |
| [22] | Jojic, V., Saria, S., & Koller, D. (2011). Convex envelopes of complexity controlling penalties: The case against premature envelopment. In International Conference on Artificial Intelligence and Statistics |
| [23] | Ke, Q., & Kanade, T. (2005). Robust l1 norm factorization in the presence of outliers and missing data by alternative convex programming. In IEEE Conference on Computer Vision and Pattern Recognition |
| [24] | Keshavan, RH; Montanari, A; Oh, S, Matrix completion from a few entries, IEEE Transactions on Information Theory, 56, 2980-2998, (2010) · Zbl 1242.62069 · doi:10.1109/TIT.2010.2046205 |
| [25] | Lai, H., Pan, Y., Lu, C., Tang, Y., & Yan, S. (2014). Efficient k-support matrix pursuit. In European Conference on Computer Vision, vol. 8690, 2014 |
| [26] | Larsson, V., Bylow, E., Olsson, C., & Kahl, F. (2014). Rank minimization with structured data patterns. In European Conference on Computer Vision |
| [27] | Larsson, V., & Olsson, C. (2015). Convex envelopes for low rank approximation. In International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition · Zbl 1398.68586 |
| [28] | Lin, Z., Chen, M., & Ma, Y. (2010). The augmented lagrange multiplier method for exact recovery of corrupted low rank matrices. Mathematical Programming. http://arxiv.org/abs/1009.5055. |
| [29] | Mazumder, R; Hastie, T; Tibshirani, R, Spectral regularization algorithms for learning large incomplete matrices, Journal of Machine Learning Research, 11, 2287-2322, (2010) · Zbl 1242.68237 |
| [30] | McDonald, A.M., Pontil, M., & Stamos, D. (2014). Spectral k-support norm regularization. In Advances in Neural Information Processing Systems · Zbl 1392.68356 |
| [31] | Okatani, T; Deguchi, K, On the wiberg algorithm for factorization with missing data, International Journal of Computer Vision, 72, 329-337, (2007) · Zbl 1477.68404 · doi:10.1007/s11263-006-9785-5 |
| [32] | Okatani, T., Yoshida, T., & Deguchi, K. (2011). Efficient algorithm for low-rank matrix factorization with missing components and performance comparison of latest algorithms. In Proceedings of the International Conference on Computer Vision |
| [33] | Olsen, S; Bartoli, A, Implicit non-rigid structure-from-motion with priors, Journal of Mathematical Imaging and Vision, 31, 233-244, (2008) · Zbl 1446.68165 · doi:10.1007/s10851-007-0060-3 |
| [34] | Olsson, C., & Oskarsson, M. (2009) A convex approach to low rank matrix approximation with missing data. In Scandinavian Conference on Image Analysis |
| [35] | Recht, B; Fazel, M; Parrilo, PA, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, 52, 471-501, (2010) · Zbl 1198.90321 · doi:10.1137/070697835 |
| [36] | Rockafellar, R. (1997). Convex Analysis. Princeton: Princeton University Press. · Zbl 0932.90001 |
| [37] | Strelow, D. (2012). General and nested Wiberg minimization. In IEEE Conference on Computer Vision and Pattern Recognition |
| [38] | Sturm, JF, Using sedumi 1.02, a Matlab toolbox for optimization over symmetric cones, Optimization Methods and Software, 11-12, 625-653, (1999) · Zbl 0973.90526 · doi:10.1080/10556789908805766 |
| [39] | The MOSEK optimization toolbox for MATLAB manual. (2016). www.mosek.com |
| [40] | Tomasi, C; Kanade, T, Shape and motion from image streams under orthography: A factorization method, International Journal of Computer Vision, 9, 137-154, (1992) · doi:10.1007/BF00129684 |
| [41] | Wang, S., Liu, D., & Zhang, Z. (2013). Nonconvex relaxation approaches to robust matrix recovery. In International Joint Conference on Artificial Intelligence |
| [42] | Wiberg, T. (2013). Computation of principal components when data are missing. In Proceedings of Second Symposium on Computational Statistics · Zbl 0385.62038 |
| [43] | Yan, J; Pollefeys, M, A factorization-based approach for articulated nonrigid shape, motion and kinematic chain recovery from video, IEEE Transactions on Pattern Analysis and Machine Intelligence, 30, 865-877, (2008) · doi:10.1109/TPAMI.2007.70739 |
| [44] | Zheng, Y., Liu, G., Sugimoto, S., Yan, S., & Okutomi, M. (2012). Practical low-rank matrix approximation under robust \(L_1\)-norm. In IEEE Conference on Computer Vision and Pattern Recognition |
| [45] | Zou, H; Hastie, T, Regularization and variable selection via the elastic net, Journal of the Royal Statistical Society B, 67, 301-320, (2005) · Zbl 1069.62054 · doi:10.1111/j.1467-9868.2005.00503.x |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
