NDLI: The Convex Geometry of Linear Inverse Problems

Please wait, while we are loading the content...

The Convex Geometry of Linear Inverse Problems

Content Provider	Springer Nature Link
Author	Chandrasekaran, Venkat Willsky, Alan S. Recht, Benjamin Parrilo, Pablo A.
Copyright Year	2012
Abstract	In applications throughout science and engineering one is often faced with the challenge of solving an ill-posed inverse problem, where the number of available measurements is smaller than the dimension of the model to be estimated. However in many practical situations of interest, models are constrained structurally so that they only have a few degrees of freedom relative to their ambient dimension. This paper provides a general framework to convert notions of simplicity into convex penalty functions, resulting in convex optimization solutions to linear, underdetermined inverse problems. The class of simple models considered includes those formed as the sum of a few atoms from some (possibly infinite) elementary atomic set; examples include well-studied cases from many technical fields such as sparse vectors (signal processing, statistics) and low-rank matrices (control, statistics), as well as several others including sums of a few permutation matrices (ranked elections, multiobject tracking), low-rank tensors (computer vision, neuroscience), orthogonal matrices (machine learning), and atomic measures (system identification). The convex programming formulation is based on minimizing the norm induced by the convex hull of the atomic set; this norm is referred to as the atomic norm. The facial structure of the atomic norm ball carries a number of favorable properties that are useful for recovering simple models, and an analysis of the underlying convex geometry provides sharp estimates of the number of generic measurements required for exact and robust recovery of models from partial information. These estimates are based on computing the Gaussian widths of tangent cones to the atomic norm ball. When the atomic set has algebraic structure the resulting optimization problems can be solved or approximated via semidefinite programming. The quality of these approximations affects the number of measurements required for recovery, and this tradeoff is characterized via some examples. Thus this work extends the catalog of simple models (beyond sparse vectors and low-rank matrices) that can be recovered from limited linear information via tractable convex programming.
Ending Page	849
Page Count	45
Starting Page	805
File Format	PDF
ISSN	16153375
e-ISSN	16153383
Journal	Foundations of Computational Mathematics
Issue Number	6
Volume Number	12
Language	English
Publisher	Springer-Verlag
Publisher Date	2012-10-16
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Semidefinite programming Economics general Approximation by arbitrary linear expressions Geometric probability and stochastic geometry Linear and Multilinear Algebras, Matrix Theory Real algebraic geometry Convex programming Convex optimization Numerical Analysis Computer Science Convex functions and convex programs Atomic norms Math Applications in Computer Science Applications of Mathematics Gaussian width Symmetry
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Analysis Computational Theory and Mathematics Computational Mathematics

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

Central Swaths : A Generalization of the Central Path

Sharp MSE Bounds for Proximal Denoising

Probabilistic Analysis of the Grassmann Condition Number

Convex Optimization on Banach Spaces

Robust Computation of Linear Models by Convex Relaxation

Self-Concordant Barriers for Convex Approximations of Structured Convex Sets

Primal Central Paths and Riemannian Distances for Convex Sets

Whitney Estimates for Convex Domains with Applications to Multivariate Piecewise Polynomial Approximation

Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals

The Convex Geometry of Linear Inverse Problems

Similar Documents

Central Swaths : A Generalization of the Central Path

Sharp MSE Bounds for Proximal Denoising

Probabilistic Analysis of the Grassmann Condition Number

Convex Optimization on Banach Spaces

Robust Computation of Linear Models by Convex Relaxation

Self-Concordant Barriers for Convex Approximations of Structured Convex Sets

Primal Central Paths and Riemannian Distances for Convex Sets

Whitney Estimates for Convex Domains with Applications to Multivariate Piecewise Polynomial Approximation

Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals

The Convex Geometry of Linear Inverse Problems