June, 2014. arXiv:1209.0377 [cs, math]

Paper abstract bibtex

Paper abstract bibtex

In this paper, we establish the following perturbation result concerning the singular values of a matrix: Let $A,B {\}in {\}mathbb\{R\}{\textasciicircum}\{m{\}times n\}$ be given matrices, and let $f:{\}mathbb\{R\}_+{\}rightarrow{\}mathbb\{R\}_+$ be a concave function satisfying $f(0)=0$. Then, we have $$ \sum_\i=1\\textasciicircum\\min\\m,n\\\ \big\textbar f(\sigma_i(A)) - f(\sigma_i(B)) \big\textbar \le \sum_\i=1\\textasciicircum\\min\\m,n\\\ f(\sigma_i(A-B)), $$ where ${\}sigma_i({\}cdot)$ denotes the $i$–th largest singular value of a matrix. This answers an open question that is of interest to both the compressive sensing and linear algebra communities. In particular, by taking $f({\}cdot)=({\}cdot){\textasciicircum}p$ for any $p {\}in (0,1]$, we obtain a perturbation inequality for the so–called Schatten $p$–quasi–norm, which allows us to confirm the validity of a number of previously conjectured conditions for the recovery of low–rank matrices via the popular Schatten $p$–quasi–norm heuristic. We believe that our result will find further applications, especially in the study of low–rank matrix recovery.

@misc{yue_perturbation_2014, title = {A {Perturbation} {Inequality} for the {Schatten}-p {Quasi}-{Norm} and {Its} {Applications} to {Low}-{Rank} {Matrix} {Recovery}}, url = {http://arxiv.org/abs/1209.0377}, abstract = {In this paper, we establish the following perturbation result concerning the singular values of a matrix: Let \$A,B {\textbackslash}in {\textbackslash}mathbb\{R\}{\textasciicircum}\{m{\textbackslash}times n\}\$ be given matrices, and let \$f:{\textbackslash}mathbb\{R\}\_+{\textbackslash}rightarrow{\textbackslash}mathbb\{R\}\_+\$ be a concave function satisfying \$f(0)=0\$. Then, we have \$\$ {\textbackslash}sum\_\{i=1\}{\textasciicircum}\{{\textbackslash}min{\textbackslash}\{m,n{\textbackslash}\}\} {\textbackslash}big{\textbar} f({\textbackslash}sigma\_i(A)) - f({\textbackslash}sigma\_i(B)) {\textbackslash}big{\textbar} {\textbackslash}le {\textbackslash}sum\_\{i=1\}{\textasciicircum}\{{\textbackslash}min{\textbackslash}\{m,n{\textbackslash}\}\} f({\textbackslash}sigma\_i(A-B)), \$\$ where \${\textbackslash}sigma\_i({\textbackslash}cdot)\$ denotes the \$i\$--th largest singular value of a matrix. This answers an open question that is of interest to both the compressive sensing and linear algebra communities. In particular, by taking \$f({\textbackslash}cdot)=({\textbackslash}cdot){\textasciicircum}p\$ for any \$p {\textbackslash}in (0,1]\$, we obtain a perturbation inequality for the so--called Schatten \$p\$--quasi--norm, which allows us to confirm the validity of a number of previously conjectured conditions for the recovery of low--rank matrices via the popular Schatten \$p\$--quasi--norm heuristic. We believe that our result will find further applications, especially in the study of low--rank matrix recovery.}, language = {en}, urldate = {2023-07-10}, publisher = {arXiv}, author = {Yue, Man-Chung and So, Anthony Man-Cho}, month = jun, year = {2014}, note = {arXiv:1209.0377 [cs, math]}, keywords = {Computer Science - Information Theory, Mathematics - Optimization and Control}, file = {Yue and So - 2014 - A Perturbation Inequality for the Schatten-\$p\$ Qua.pdf:/Users/georgehuang/Zotero/storage/E8MU73WV/Yue and So - 2014 - A Perturbation Inequality for the Schatten-\$p\$ Qua.pdf:application/pdf}, }

Downloads: 0