nach oben

Foundations of Computational Mathematics

Erschienen in:

01.10.2015

Local Convergence of an Algorithm for Subspace Identification from Partial Data

verfasst von: Laura Balzano, Stephen J. Wright

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

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Grassmannian rank-one update subspace estimation (GROUSE) is an iterative algorithm for identifying a linear subspace of \(\mathbb {R}^n\) from data consisting of partial observations of random vectors from that subspace. This paper examines local convergence properties of GROUSE, under assumptions on the randomness of the observed vectors, the randomness of the subset of elements observed at each iteration, and incoherence of the subspace with the coordinate directions. Convergence at an expected linear rate is demonstrated under certain assumptions. The case in which the full random vector is revealed at each iteration allows for much simpler analysis and is also described. GROUSE is related to incremental SVD methods and to gradient projection algorithms in optimization.

Vorheriger Artikel Construction of Interlaced Scrambled Polynomial Lattice Rules of Arbitrary High Order

Nächster Artikel Exact Support Recovery for Sparse Spikes Deconvolution

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

B. A. Ardekani, J. Kershaw, K. Kashikura, and I. Kanno, Activation detection in functional MRIusing subspace modeling and maximum likelihood estimation, IEEETransactions on Medical Imaging, 18 (1999), pp. 101–114.

L. Balzano, Handling Missing Data in High-DimensionalSubspace Modeling, PhD thesis, University of Wisconsin-Madison, May2012.

L. Balzano, R. Nowak, and B. Recht, Online identification and tracking of subspaces from highlyincomplete information, in 48th Annual Allerton Conference OnCommunication, Control, and Computing (Allerton), September 2010,pp. 704–711. Available at http://arxiv.org/abs/1006.4046.

L. Balzano, B. Recht, and R. Nowak, High-dimensional matched subspace detection when data are missing,in Proceedings of the International Symposium on Information Theory,IEEE, June 2010, pp. 1638–1642.

L. Balzano and S. J. Wright, On GROUSE andincremental SVD, in Proceedings of the 5th International Workshopon Computational Advances in Multi-Sensor Adaptive Processing(CAMSAP), 2013, pp. 1–4.

R. Basri and D. Jacobs, Lambertianreflectance and linear subspaces, IEEE Transactions on PatternAnalysis and Machine Intelligence, 25 (2003), pp. 218–233.

E. Candès and J. Romberg, Sparsity andincoherence in compressive sampling, Inverse Problems, 23 (2007),pp. 969–985.

J. P. Costeira and T. Kanade,A multibody factorization method for independently movingobjects, International Journal of Computer Vision, 29 (1998), pp.159–179.

D. Gross, Recovering low-rank matrices from fewcoefficients in any basis, IEEE Transactions on Information Theory,57 (2011), pp. 1548–1566.

10.

J. Gupchup, R. Burns, A. Terzis, and A. Szalay, Model-based event detection in wireless sensornetworks, in Proceedings of the Workshop on Data Sharing andInteroperability (DSI), 2007.

11.

Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp, Finding structure with randomness:Probabilistic algorithms for constructing approximate matrixdecompositions, SIAM Review, 53 (2011), pp. 217–288.

12.

H. Krim and M. Viberg, Two decades of arraysignal processing research: the parametric approach, IEEE SignalProcessing Magazine, 13 (1996), pp. 67–94.

13.

A. Lakhina, M. Crovella, and C. Diot, Diagnosing network-wide traffic anomalies, in Proceedings ofSIGCOMM, 2004, pp. 219–230.

14.

D. Manolakis and G. Shaw, Detectionalgorithms for hyperspectral imaging applications, IEEE SignalProcessing Magazine, 19 (2002), pp. 29–43.

15.

J. Nocedal and S. J. Wright, NumericalOptimization, Springer, New York, second ed., 2006.

16.

S. Papadimitriou, J. Sun, and C. Faloutsos,Streaming pattern discovery in multiple time-series, inProceedings of the 31st International Conference on Very Large DataBases (VLDB ’05), 2005, pp. 697–708.

17.

B. Recht, A simpler approach to matrix completion,Journal of Machine Learning Research, 12 (2011), pp. 3413–3430.

18.

G. W. Stewart and J. Sun, Matrix PerturbationTheory, Computer Science and Scientific Computing, Academic Press,New York, 1990.

19.

L. Tong and S. Perreau, Multichannel blindidentification: From subspace to maximum likelihood methods,Proceedings of the IEEE, 86 (1998), pp. 1951–1968.

20.

P. van Overschee and B. de Moor, SubspaceIdentification for Linear Systems, Kluwer Academic Publishers,Norwell, Massachusetts, 1996.

21.

L. Vandenberghe, Convex optimization techniques in systemidentification, in Proceedings of the IFAC Symposium on SystemIdentification, July 2012, pp. 71–76.

22.

G. S. Wagner and T. J. Owens, Signaldetection using multi-channel seismic data, Bulletin of theSeismological Society of America, 86 (1996), pp. 221–231.

Titel: Local Convergence of an Algorithm for Subspace Identification from Partial Data
verfasst von: Laura Balzano
Stephen J. Wright
Publikationsdatum: 01.10.2015
Verlag: Springer US
Erschienen in: Foundations of Computational Mathematics / Ausgabe 5/2015
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-014-9227-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 "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 5/2015

Exact Support Recovery for Sparse Spikes Deconvolution

Construction of Interlaced Scrambled Polynomial Lattice Rules of Arbitrary High Order

The Persistent Homology of a Self-Map

Robust boundary tracking for reachable sets of nonlinear differential inclusions

Improved Bounds on Sample Size for Implicit Matrix Trace Estimators

Zigzag Zoology: Rips Zigzags for Homology Inference

Premium Partner