nach oben

Foundations of Computational Mathematics

Erschienen in:

01.04.2015

Robust Computation of Linear Models by Convex Relaxation

verfasst von: Gilad Lerman, Michael B. McCoy, Joel A. Tropp, Teng Zhang

Erschienen in: Foundations of Computational Mathematics | Ausgabe 2/2015

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Consider a data set of vector-valued observations that consists of noisy inliers, which are explained well by a low-dimensional subspace, along with some number of outliers. This work describes a convex optimization problem, called reaper, that can reliably fit a low-dimensional model to this type of data. This approach parameterizes linear subspaces using orthogonal projectors and uses a relaxation of the set of orthogonal projectors to reach the convex formulation. The paper provides an efficient algorithm for solving the reaper problem, and it documents numerical experiments that confirm that reaper can dependably find linear structure in synthetic and natural data. In addition, when the inliers lie near a low-dimensional subspace, there is a rigorous theory that describes when reaper can approximate this subspace.

Vorheriger Artikel A Milstein Scheme for SPDEs

Nächster Artikel Multi-level Quasi-Monte Carlo Finite Element Methods for a Class of Elliptic PDEs with Random Coefficients

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 "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

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

Nur mit Berechtigung zugänglich

A data set is simply a finite multiset, that is, a finite set with repeated elements allowed.

In both figures, \(N_{\mathrm{out}}\) increases in increments of 20, while \(N_{\mathrm{in}}\) increases in increments of 2.

In this experiment, \(N_{\mathrm{in}}\) increases in increments of 2 while \(N_{\mathrm{out}}\) increases in increments of \(20\).

More precisely, the inlier-to-outlier ratio must exceed \((121\mu /9) d \), where \(\mu \ge 1\) depends on the data.

Ammann, L.P.: Robust singular value decompositions: A new approach to projection pursuit. J. Amer. Statist. Assoc. 88(422), 505–514 (1993). http://www.jstor.org/stable/2290330

Bargiela, A., Hartley, J.K.: Orthogonal linear regression algorithm based on augmented matrix formulation. Comput. Oper. Res. 20, 829–836 (1993). doi:10.1016/0305-0548(93)90104-Q. http://dl.acm.org/citation.cfm?id=165819.165826

Basri, R., Jacobs, D.: Lambertian reflectance and linear subspaces. IEEE Trans. Pattern Anal. Mach. Intell. 25(2), 218–233 (2003)

Bhatia, R.: Matrix Analysis. No. 169 in Graduate Texts in Mathematics. Springer, New York (1997)

Björck, Å.: Numerical Methods for Least Squares Problems. Society for Industrial and Applied Mathematics, Philadelphia, PA (1996)

Bogachev, V.I.: Gaussian Measures, Mathematical Surveys and Monographs, vol. 62. American Mathematical Society, Providence, RI (1998)

Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer Series in Operations Research. Springer (2000)

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), 1–122 (2010). doi:10.1561/2200000016. http://www.nowpublishers.com/product.aspx?product=MAL&doi=2200000016

Brubaker, S.C.: Robust PCA and clustering in noisy mixtures. In: Proc. 20th Ann. ACM-SIAM Symp. Discrete Algorithms, SODA ’09, pp. 1078–1087. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2009). http://portal.acm.org/citation.cfm?id=1496770.1496887

10.

Caltech 101. Online (2006). http://www.vision.caltech.edu/Image_Datasets/Caltech101/

11.

Candès, E.J., Li, X., Ma, Y., Wright, J.: Robust principal component analysis? J. Assoc. Comput. Mach. 58(3) (2011)

12.

Cavalier, T.M., Melloy, B.J.: An iterative linear programming solution to the Euclidean regression model. Comput. Oper. Res. 18, 655–661 (1991)

13.

Chan, T.F., Mulet, P.: On the convergence of the lagged diffusivity fixed point method in total variation image restoration. SIAM J. Numer. Anal. 36, 354–367 (1999). doi:10.1137/S0036142997327075

14.

Chandrasekaran, V., Sanghavi, S., Parrilo, P.A., Willsky, A.S.: Rank-sparsity incoherence for matrix decomposition. SIAM J. Optim. 21(2), 572–596 (2011). doi:10.1137/090761793

15.

Cook, R.D., Weisberg, S.: Residuals and influence in regression. Chapman and Hall, New York (1982)

16.

Costeira, J., Kanade, T.: A multibody factorization method for independently moving objects. Int. J. Comput. Vision 29(3), 159–179 (1998)

17.

Coudron, M., Lerman, G.: On the sample complexity of robust pca. In: NIPS, pp. 3230–3238 (2012)

18.

Croux, C., Filzmoser, P., Oliveira, M.: Algorithms for projection pursuit robust principal component analysis. Chemometrics Intell. Lab. Sys. 87(2), 218–225 (2007)

19.

Croux, C., Haesbroeck, G.: Principal component analysis based on robust estimators of the covariance or correlation matrix: Influence functions and efficiencies. Biometrika 87, 603–618 (2000)

20.

Davidson, K.R., Szarek, S.J.: Local operator theory, random matrices and Banach spaces. In: Handbook of the geometry of Banach spaces, Vol. I, pp. 317–366. North-Holland, Amsterdam (2001). doi:10.1016/S1874-5849(01)80010-3

21.

Davidson, K.R., Szarek, S.J.: Addenda and corrigenda to: “Local operator theory, random matrices and Banach spaces” [in Handbook of the geometry of Banach spaces, Vol. I, 317–366, North-Holland, Amsterdam, 2001; MR1863696 (2004f:47002a)]. In: Handbook of the geometry of Banach spaces, Vol. 2, pp. 1819–1820. North-Holland, Amsterdam (2003)

22.

Davies, P.L.: Asymptotic behaviour of S-estimates of multivariate location parameters and dispersion matrices. Ann. Statist. 15(3), 1269–1292 (1987). http://www.jstor.org/stable/2241828

23.

Deerwester, S., Dumais, S., Landauer, T., Furna, G., Beck, L.: Improving Information Retrieval with Latent Semantic Indexing. In: C.L. Borgman, E.Y.H. Pai (eds.) Information & Technology Planning for the Second 50 Years Proceedings of the 51st Annual Meeting of the American Society for Information Science, vol. 25. Learned Information Inc, Atlanta, Georgia (1988)

24.

Devlin, S.J., Gnandesikan, R., Kettenring, J.R.: Robust estimation of dispersion matrices and principal components. J. Amer. Statist. Assoc. 76(374), 354–362 (1981). http://www.jstor.org/stable/2287836

25.

Ding, C., Zhou, D., He, X., Zha, H.: R1-PCA: Rotational invariant \(L_1\)-norm principal component analysis for robust subspace factorization. In: ICML ’06: Proc. 23rd Int. Conf. Machine Learning, pp. 281–288. Association for Computing Machinery, Pittsburgh, PA (2006). doi:10.1145/1143844.1143880

26.

Dodge, Y.: An introduction to \(l_1\)-norm based statistical data analysis. Comput. Statist. Data Anal. 5(4), 239–253 (1987). doi:10.1016/0167-9473(87)90048-X. http://www.sciencedirect.com/science/article/pii/016794738790048X

27.

Eckart, C., Young, G.: A principal axis transformation for non-hermitian matrices. Bull. Amer. Math. Soc. 45(2), 118–121 (1939)

28.

Epstein, R., Hallinan, P., Yuille, A.L.: \(5 \pm 2\) eigenimages suffice: An empirical investigation of low-dimensional lighting models. In: Physics-Based Modeling in Computer Vision, 1995, Proceedings of the Workshop on, p. 108 (1995). doi:10.1109/PBMCV.1995.514675

29.

Eriksson, A., van den Hengel, A.: Efficient computation of robust low-rank matrix approximations in the presence of missing data using the \(l_1\) norm. In: Proc. 2010 IEEE Conf. Computer Vision and Pattern Recognition, pp. 771–778 (2010). doi:10.1109/CVPR.2010.5540139

30.

Fei-Fei, L., Fergus, R., Perona, P.: Learning generative visual models from a few training examples: an incremental bayesian approach tested on 101 object categories. In: CVPR 2004, Workshop on Generative-Model Based Vision. IEEE (2004)

31.

Fischler, M., Bolles, R.: Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Comm. Assoc. Comput. Mach. 24(6), 381–395 (1981)

32.

Goemans, M.X., Williamson, D.P.: Improved approximation for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42, 1115–1145 (1995)

33.

Grant, M., Boyd, S.: Graph implementations for nonsmooth convex programs. In: V. Blondel, S. Boyd, H. Kimura (eds.) Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences, pp. 95–110. Springer, London (2008). http://stanford.edu/~boyd/graph_dcp.html

34.

Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 1.21. http://cvxr.com/cvx (2010)

35.

Halko, N., Martinsson, P.G., Tropp, J.A.: Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217–288 (2011)

36.

Harter, H.L.: The method of least squares and some alternatives: Part I. Int. Statist. Rev. 42(2), 147–174 (1974)

37.

Harter, H.L.: The method of least squares and some alternatives: Part II. Int. Statist. Rev. 42(3), 235–282 (1974)

38.

Ho, J., Yang, M., Lim, J., Lee, K., Kriegman, D.: Clustering appearances of objects under varying illumination conditions. In: Proc. 2003 IEEE Int. Conf. Computer Vision and Pattern Recognition, vol. 1, pp. 11–18 (2003)

39.

Huber, P.J., Ronchetti, E.M.: Robust Statistics, 2nd edn. Wiley Series in Probability and Statistics. Wiley, Hoboken, NJ (2009). doi:10.1002/9780470434697

40.

van Huffel, S., Vandewalle, J.: Total Least Squares: Computational Aspects and Analysis. Society for Industrial and Applied Mathematics, Philadelphia, PA (1987)

41.

Jolliffe, I.T.: Principal Component Analysis, 2nd edn. Springer, Berlin (2002)

42.

Kershaw, D.: Some extensions of W. Gautschi’s inequalities for the gamma function. Math. Comput. 41(164), pp. 607–611 (1983). http://www.jstor.org/stable/2007697

43.

Kwak, N.: Principal component analysis based on \(L_1\)-norm maximization. IEEE Trans. Pattern Anal. Mach. Intell. 30(9), 1672–1680 (2008). doi:10.1109/TPAMI.2008.114

44.

Ledoux, M., Talagrand, M.: Probability in Banach spaces, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 23. Springer, Berlin (1991). Isoperimetry and processes

45.

Lee, K.C., Ho, J., Kriegman, D.: Acquiring linear subspaces for face recognition under variable lighting. IEEE Trans. Pattern Anal. Mach. Intell. 27(5), 684–698 (2005)

46.

Lerman, G., McCoy, M.B., Tropp, J.A., Zhang, T.: Robust computation of linear models, or how to find a needle in a haystack (2012). Available at arxiv:1202.4044v1

47.

Lerman, G., Zhang, T.: \(\ell _p\)-Recovery of the most significant subspace among multiple subspaces with outliers. Constr. Approx. (2014). doi:10.1007/s00365-014-9242-6

48.

Lerman, G., Zhang, T.: Robust recovery of multiple subspaces by geometric \(\ell _p\) minimization. Ann. Statist. 39(5), 2686–2715 (2011)

49.

Li, G., Chen, Z.: Projection-pursuit approach to robust dispersion matrices and principal components: Primary theory and Monte Carlo. J. Amer. Statist. Assoc. 80(391), 759–766 (1985). doi:10.2307/2288497

50.

Liu, G., Lin, Z., Yan, S., Sun, J., Yu, Y., Ma, Y.: Robust recovery of subspace structures by low-rank representation. IEEE Trans. Pattern Anal. Mach. Intell. 35(1), 171–184 (2013). doi:10.1109/TPAMI.2012.88

51.

Locantore, N., Marron, J.S., Simpson, D.G., Tripoli, N., Zhang, J.T., Cohen, K.L.: Robust principal component analysis for functional data. Test 8(1), 1–73 (1999). doi:10.1007/BF02595862. With discussion and a rejoinder by the authors

52.

Lovasz, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1(2), 166–190 (1991). doi:10.1137/0801013. http://link.aip.org/link/?SJE/1/166/1

53.

Maronna, R.: Principal components and orthogonal regression based on robust scales. Technometrics 47(3), 264–273 (2005). doi:10.1198/004017005000000166

54.

Maronna, R.A.: Robust M-estimators of multivariate location and scatter. Ann. Statist. 4(1), 51–67 (1976). http://www.jstor.org/stable/2957994

55.

Maronna, R.A., Martin, D.R., Yohai, V.J.: Robust Statistics. Wiley Series in Probability and Statistics. Wiley, Chichester (2006). doi:10.1002/0470010940. Theory and methods

56.

McCoy, M., Tropp, J.A.: Two proposals for robust PCA using semidefinite programming. Electron. J. Statist. 5, 1123–1160 (2011)

57.

Novembre, J., Johnson, T., Bryc, K., Kutalik, Z., Boyko, A.R., Auton, A., Indap, A., King, K.S., Bergmann, S., Nelson, M., Stephens, M., Bustamante, C.D.: Genes mirror geography within Europe. Nature 456(7218), 98–101 (2008). doi:10.1038/nature07331. http://www.ncbi.nlm.nih.gov/pubmed/18758442?itool=EntrezSystem2.PEntrez.Pubmed.Pubmed_ResultsPanel.Pubmed_RVDocSum&ordinalpos=8

58.

Nyquist, H.: Least orthogonal absolute deviations. Comput. Statist. Data Anal. 6(4), 361–367 (1988). doi:10.1016/0167-9473(88)90076-X. http://www.sciencedirect.com/science/article/pii/016794738890076X

59.

Osborne, M.R., Watson, G.A.: An analysis of the total approximation problem in separable norms, and an algorithm for the total \(l_1 \) problem. SIAM J. Sci. Statist. Comput. 6(2), 410–424 (1985). doi:10.1137/0906029. http://link.aip.org/link/?SCE/6/410/1

60.

Overton, M.L., Womersley, R.S.: On the sum of the largest eigenvalues of a symmetric matrix. SIAM J. Matrix Anal. Appl. 13(1), 41–45 (1992)

61.

Price, A.L., Patterson, N.J., Plenge, R.M., Weinblatt, M.E., Shadick, N.A., Reich, D.: Principal components analysis corrects for stratification in genome-wide association studies. Nature Genetics 38(8), 904–909 (2006). http://www.ncbi.nlm.nih.gov/pubmed/16862161

62.

Rockafellar, R.T.: Convex analysis. Princeton Mathematical Series, No. 28. Princeton University Press, Princeton, N.J. (1970)

63.

Rousseeuw, P.J.: Least median of squares regression. J. Amer. Statist. Assoc. 79(388), 871–880 (1984)

64.

Rousseeuw, P.J., Leroy, A.M.: Robust Regression and Outlier Detection. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. Wiley, New York (1987)

65.

Späth, H., Watson, G.A.: On orthogonal linear approximation. Numer. Math. 51, 531–543 (1987). doi:10.1007/BF01400354. http://dl.acm.org/citation.cfm?id=34311.34315

66.

Torre, F.D.L., Black, M.J.: Robust principal component analysis for computer vision. In: Proc. 8th IEEE Conf. Computer Vision, vol. 1, pp. 362–369 vol. 1 (2001). doi:10.1109/ICCV.2001.937541

67.

Torre, F.D.L., Black, M.J.: A framework for robust subspace learning. Int. J. Comput. Vision 54, 117–142 (2003). doi:10.1023/A:1023709501986

68.

Tropp, J.A.: Just relax: convex programming methods for identifying sparse signals in noise. IEEE Trans. Inform. Theory 52(3), 1030–1051 (2006). doi:10.1109/TIT.2005.864420

69.

Tropp, J.A.: Corrigendum in “just relax: Convex programming methods for identifying sparse signals in noise”. IEEE Trans. Inform. Theory 55(2) (2009)

70.

Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2003)

71.

Voss, H., Eckhardt, U.: Linear convergence of generalized Weiszfeld’s method. Computing 25, 243–251 (1980). doi:10.1007/BF02242002

72.

Wang, L., Singer, A.: Exact and stable recovery of rotations for robust synchronization. Information and Inference (2013). doi:10.1093/imaiai/iat005

73.

Watson, G.A.: Some problems in orthogonal distance and non-orthogonal distance regression. In: Proc. 2001 Symp. Algorithms for Approximation IV. Defense Technical Information Center (2001). http://books.google.com/books?id=WKKWGwAACAAJ

74.

Watson, G.A.: On the Gauss-Newton method for \(l_1\) orthogonal distance regression. IMA J. Numer. Anal. 22(3), 345–357 (2002). doi:10.1093/imanum/22.3.345. http://imajna.oxfordjournals.org/content/22/3/345.abstract

75.

Witten, D., Tibshirani, R., Hastie, T.: A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis. Biostat. 10(3), 515–534 (2009)

76.

Xu, H., Caramanis, C., Mannor, S.: Principal Component Analysis with Contaminated Data: The High Dimensional Case. In: Proc. 2010 Conf. Learning Theory. OmniPress, Haifa (2010)

77.

Xu, H., Caramanis, C., Sanghavi, S.: Robust PCA via outlier pursuit. In: J. Lafferty, C.K.I. Williams, J. Shawe-Taylor, R. Zemel, A. Culotta (eds.) Neural Information Processing Systems 23, pp. 2496–2504. MIT Press, Vancouver (2010)

78.

Xu, H., Caramanis, C., Sanghavi, S.: Robust PCA via outlier pursuit. IEEE Trans. Inform. Theory 58(5), 3047–3064 (2012)

79.

Xu, L., Yuille, A.L.: Robust principal component analysis by self-organizing rules based on statistical physics approach. IEEE Trans. Neural Networks 6(1), 131–143 (1995). doi:10.1109/72.363442

80.

Xu, L., Yuille, A.L.: Robust principal component analysis by self-organizing rules based on statistical physics approach. IEEE Trans. Neural Networks 6(1), 131–143 (1995). doi:10.1109/72.363442

81.

Zhang, T., Szlam, A., Lerman, G.: Median \(K\)-flats for hybrid linear modeling with many outliers. In: Proc. 12th IEEE Int. Conf. Computer Vision, pp. 234–241. Kyoto (2009). doi:10.1109/ICCVW.2009.5457695

Titel: Robust Computation of Linear Models by Convex Relaxation
verfasst von: Gilad Lerman
Michael B. McCoy
Joel A. Tropp
Teng Zhang
Publikationsdatum: 01.04.2015
Verlag: Springer US
Erschienen in: Foundations of Computational Mathematics / Ausgabe 2/2015
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-014-9221-0

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 "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2015

Higher-Order Averaging, Formal Series and Numerical Integration III: Error Bounds

Nonlinear Approximation Rates and Besov Regularity for Elliptic PDEs on Polyhedral Domains

Multi-level Quasi-Monte Carlo Finite Element Methods for a Class of Elliptic PDEs with Random Coefficients

Sparse Differential Resultant for Laurent Differential Polynomials

Stroboscopic Averaging for the Nonlinear Schrödinger Equation

A Milstein Scheme for SPDEs

Premium Partner