Local Convergence of an Algorithm for Subspace Identification from Partial Data

详细信息    查看全文

• 作者：Laura Balzano ; Stephen J. Wright
• 关键词：Subspace identification ; Optimization ; Incomplete data ; 90C52 ; 65Y20 ; 68W20
• 刊名：Foundations of Computational Mathematics
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：15
• 期：5
• 页码：1279-1314
• 全文大小：1,004 KB
• 参考文献：1.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鈥?14.
  2.L. Balzano , Handling Missing Data in High-DimensionalSubspace Modeling, PhD thesis, University of Wisconsin-Madison, May2012.
  3.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鈥?11. Available at http://鈥媋rxiv.鈥媜rg/鈥媋bs/鈥?006.鈥?046 .
  4.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鈥?642.
  5.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鈥?.
  6.R. Basri and D. Jacobs , Lambertianreflectance and linear subspaces, IEEE Transactions on PatternAnalysis and Machine Intelligence, 25 (2003), pp. 218鈥?33.
  7.E. Cand猫s and J. Romberg , Sparsity andincoherence in compressive sampling, Inverse Problems, 23 (2007),pp. 969鈥?85.
  8.J. P. Costeira and T. Kanade ,A multibody factorization method for independently movingobjects, International Journal of Computer Vision, 29 (1998), pp.159鈥?79.
  9.D. Gross , Recovering low-rank matrices from fewcoefficients in any basis, IEEE Transactions on Information Theory,57 (2011), pp. 1548鈥?566.
  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鈥?88.
  12.H. Krim and M. Viberg , Two decades of arraysignal processing research: the parametric approach, IEEE SignalProcessing Magazine, 13 (1996), pp. 67鈥?4.
  13.A. Lakhina , M. Crovella , and C. Diot , Diagnosing network-wide traffic anomalies, in Proceedings ofSIGCOMM, 2004, pp. 219鈥?30.
  14.D. Manolakis and G. Shaw , Detectionalgorithms for hyperspectral imaging applications, IEEE SignalProcessing Magazine, 19 (2002), pp. 29鈥?3.
  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 鈥?5), 2005, pp. 697鈥?08.
  17.B. Recht , A simpler approach to matrix completion,Journal of Machine Learning Research, 12 (2011), pp. 3413鈥?430.
  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鈥?968.
  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鈥?6.
  22.G. S. Wagner and T. J. Owens , Signaldetection using multi-channel seismic data, Bulletin of theSeismological Society of America, 86 (1996), pp. 221鈥?31.
  
• 作者单位：Laura Balzano (1)
  Stephen J. Wright (2)
  
  1. Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI, USA
  2. Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Numerical Analysis
  Computer Science, general
  Math Applications in Computer Science
  Linear and Multilinear Algebras and Matrix Theory
  Applications of Mathematics
  
• 出版者：Springer New York
• ISSN：1615-3383

文摘

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. Keywords Subspace identification Optimization Incomplete data