NDLI: Diagonal and low-rank decompositions and fitting ellipsoids to random points

Content Provider	IEEE Xplore Digital Library
Author	Saunderson, J. Parrilo, P.A. Willsky, A.S.
Copyright Year	2013
Description	Author affiliation: Dept. of Electr. Eng. & Comput. Sci., Massachusetts Inst. of Technol., Cambridge, MA, USA (Saunderson, J.; Parrilo, P.A.; Willsky, A.S.)
Abstract	Identifying a subspace containing signals of interest in additive noise is a basic system identification problem. Under natural assumptions, this problem is known as the Frisch scheme and can be cast as decomposing an n × n positive definite matrix as the sum of an unknown diagonal matrix (the noise covariance) and an unknown low-rank matrix (the signal covariance). Our focus in this paper is a natural class of random instances, where the low-rank matrix has a uniformly distributed random column space. In this setting we analyze the behavior of a well-known convex optimization-based heuristic for diagonal and low-rank decomposition called minimum trace factor analysis (MTFA). Conditions for the success of MTFA have an appealing geometric reformulation as finding a (convex) ellipsoid that exactly interpolates a given set of n points. Under the random model, the points are chosen according to a Gaussian distribution. Numerical experiments suggest a remarkable threshold phenomenon: if the (random) column space of the n × n lowrank matrix has codimension as small as 2√n then with high probability MTFA successfully performs the decomposition task, otherwise it fails with high probability. In this work we provide numerical evidence and prove partial results in this direction, showing that with high probability MTFA recovers such random low-rank matrices of corank at least $cn^{β}$ for β ϵ (5/6, 1) and some constant c.
Sponsorship	IEEE Control Syst. Soc.
Starting Page	6031
Ending Page	6036
File Size	373734
Page Count	6
File Format	PDF
ISBN	9781467357142
ISSN	07431546
e-ISBN	9781467357173
DOI	10.1109/CDC.2013.6760842
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-12-10
Publisher Place	Italy
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Ellipsoids Matrix decomposition Symmetric matrices Standards Covariance matrices Vectors Coherence
Content Type	Text
Resource Type	Article
Subject	Control and Optimization Control and Systems Engineering Modeling and Simulation

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Diagonal and Low-Rank Decompositions and Fitting Ellipsoids to Random Points

DIAGONAL AND LOW-RANK MATRIX DECOMPOSITIONS, CORRELATION MATRICES, AND ELLIPSOID FITTING

Diagonal and low-rank matrix decompositions, correlation matrices, and ellipsoid fitting.

DIAGONAL AND LOW-RANK MATRIX DECOMPOSITIONS, CORRELATION MATRICES, AND ELLIPSOID FITTING (2012)

Low-rank optimization for distance matrix completion

Adaptive beamforming using fast low-rank covariance matrix approximations

Errors-in-variables identification using covariance matching and structural equation modeling

Sparse matrix decompositions for clustering

A simple approach to H∞ analysis

Diagonal and low-rank decompositions and fitting ellipsoids to random points

Similar Documents

Diagonal and Low-Rank Decompositions and Fitting Ellipsoids to Random Points

DIAGONAL AND LOW-RANK MATRIX DECOMPOSITIONS, CORRELATION MATRICES, AND ELLIPSOID FITTING

Diagonal and low-rank matrix decompositions, correlation matrices, and ellipsoid fitting.

DIAGONAL AND LOW-RANK MATRIX DECOMPOSITIONS, CORRELATION MATRICES, AND ELLIPSOID FITTING (2012)

Low-rank optimization for distance matrix completion

Adaptive beamforming using fast low-rank covariance matrix approximations

Errors-in-variables identification using covariance matching and structural equation modeling

Sparse matrix decompositions for clustering

A simple approach to H∞ analysis

Diagonal and low-rank decompositions and fitting ellipsoids to random points