nach oben

International Journal of Computer Vision

Erschienen in:

01.11.2016

Convex Low Rank Approximation

verfasst von: Viktor Larsson, Carl Olsson

Erschienen in: International Journal of Computer Vision | Ausgabe 2/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Shape Retrieval of Non-rigid 3D Human Models

Nächster Artikel Detection of Co-salient Objects by Looking Deep and Wide

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Since it is possible to restrict the minimization in X to a compact set the existence of a saddle point can be guaranteed (see Rockafellar (1997) for details).

Note that we choose \(g(k) = \mu k\) here to allow for a comparison with the nuclear norm. In general when we solve the missing data problem we use \(g(k) =\mathbb {I}(k \le r_0)\).

Here \({\mathcal {P}}_k(U)\) denotes the rows corresponding to block k.

Andersson, F., Carlsson, M., Tourneret, J. Y., & Wendt, H. (2014). A new frequency estimation method for equally and unequally spaced data. IEEE Transactions on Signal Processing, 62(21), 5761–5774.MathSciNetCrossRef

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

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

Argyriou, A., Foygel, R., & Srebro, N. (2012). Sparse prediction with the k-support norm. In Advances in Neural Information Processing Systems

Basri, R., Jacobs, D., & Kemelmacher, I. (2007). Photometric stereo with general, unknown lighting. International Journal of Computer Vision, 72(3), 239–257.CrossRef

Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1), 1–122.CrossRefMATH

Bregler, C., Hertzmann, A., & Biermann, H. (2000). Recovering non-rigid 3d shape from image streams. In IEEE Conference on Computer Vision and Pattern Recognition

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

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

Cai, J. F., Candès, E. J., & Shen, Z. (2010). A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 20(4), 1956–1982.MathSciNetCrossRefMATH

Candès, E. J., Li, X., Ma, Y., & Wright, J. (2011). Robust principal component analysis? Journal of the ACM, 58(3), 11:1–11:37.MathSciNetCrossRefMATH

Eckart, C., & Young, G. (1936). The approximation of one matrix by another of lower rank. Psychometrika, 1(3), 211–218.CrossRefMATH

Eriksson, A., & Hengel, A. (2012). Efficient computation of robust weighted low-rank matrix approximations using the \(L_1\) norm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(9), 1681–1690.CrossRef

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

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

Fazel, M., Hindi, H., & Boyd, S. P. (2001). A rank minimization heuristic with application to minimum order system approximation. In American Control Conference

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

Garg, R., Roussos, A., & Agapito, L. (2013). A variational approach to video registration with subspace constraints. International Journal of Computer Vision, 104(3), 286–314.MathSciNetCrossRefMATH

Gillis, N., & Glinuer, F. (2011). Low-rank matrix approximation with weights or missing data is np-hard. SIAM Journal on Matrix Analysis and Applications, 32, 4.MathSciNetCrossRef

Hu, Y., Zhang, D., Ye, J., Li, X., & He, X. (2013). Fast and accurate matrix completion via truncated nuclear norm regularization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(9), 2117–2130. doi:10.1109/TPAMI.2012.271.CrossRef

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

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

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

Keshavan, R. H., Montanari, A., & Oh, S. (2010). Matrix completion from a few entries. IEEE Transactions on Information Theory, 56(6), 2980–2998.MathSciNetCrossRefMATH

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

Larsson, V., Bylow, E., Olsson, C., & Kahl, F. (2014). Rank minimization with structured data patterns. In European Conference on Computer Vision

Larsson, V., & Olsson, C. (2015). Convex envelopes for low rank approximation. In International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition

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.

Mazumder, R., Hastie, T., & Tibshirani, R. (2010). Spectral regularization algorithms for learning large incomplete matrices. Journal of Machine Learning Research, 11, 2287–2322.MathSciNetMATH

McDonald, A.M., Pontil, M., & Stamos, D. (2014). Spectral k-support norm regularization. In Advances in Neural Information Processing Systems

Okatani, T., & Deguchi, K. (2007). On the wiberg algorithm for factorization with missing data. International Journal of Computer Vision, 72(3), 329–337.CrossRef

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

Olsen, S., & Bartoli, A. (2008). Implicit non-rigid structure-from-motion with priors. Journal of Mathematical Imaging and Vision, 31(2–3), 233–244. doi:10.1007/s10851-007-0060-3.MathSciNetCrossRef

Olsson, C., & Oskarsson, M. (2009) A convex approach to low rank matrix approximation with missing data. In Scandinavian Conference on Image Analysis

Recht, B., Fazel, M., & Parrilo, P. A. (2010). Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review, 52(3), 471–501.MathSciNetCrossRefMATH

Rockafellar, R. (1997). Convex Analysis. Princeton: Princeton University Press.MATH

Strelow, D. (2012). General and nested Wiberg minimization. In IEEE Conference on Computer Vision and Pattern Recognition

Sturm, J. F. (1999). Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optimization Methods and Software, 11–12, 625–653.MathSciNetCrossRefMATH

The MOSEK optimization toolbox for MATLAB manual. (2016). www.mosek.com

Tomasi, C., & Kanade, T. (1992). Shape and motion from image streams under orthography: A factorization method. International Journal of Computer Vision, 9(2), 137–154.CrossRef

Wang, S., Liu, D., & Zhang, Z. (2013). Nonconvex relaxation approaches to robust matrix recovery. In International Joint Conference on Artificial Intelligence

Wiberg, T. (2013). Computation of principal components when data are missing. In Proceedings of Second Symposium on Computational Statistics

Yan, J., & Pollefeys, M. (2008). A factorization-based approach for articulated nonrigid shape, motion and kinematic chain recovery from video. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(5), 865–877.CrossRef

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

Zou, H., & Hastie, T. (2005). Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society B, 67, 301–320.MathSciNetCrossRefMATH

Titel: Convex Low Rank Approximation
verfasst von: Viktor Larsson
Carl Olsson
Publikationsdatum: 01.11.2016
Verlag: Springer US
Erschienen in: International Journal of Computer Vision / Ausgabe 2/2016
Print ISSN: 0920-5691
Elektronische ISSN: 1573-1405
DOI: https://doi.org/10.1007/s11263-016-0904-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2016

Large-Scale Data for Multiple-View Stereopsis

Learning Dictionary of Discriminative Part Detectors for Image Categorization and Cosegmentation

Shape Retrieval of Non-rigid 3D Human Models

Trinocular Geometry Revisited

Detection of Co-salient Objects by Looking Deep and Wide

Premium Partner