A Perturbation Inequality for the Schatten-p Quasi-Norm and Its Applications to Low-Rank Matrix Recovery. Yue, M. & So, A. M. June, 2014. arXiv:1209.0377 [cs, math]![A Perturbation Inequality for the Schatten-p Quasi-Norm and Its Applications to Low-Rank Matrix Recovery [link]](https://bibbase.org/img/filetypes/link.svg "link")
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
{"_id":"CuGKTGKAvRLpLHAs7","bibbaseid":"yue-so-aperturbationinequalityfortheschattenpquasinormanditsapplicationstolowrankmatrixrecovery-2014","author_short":["Yue, M.","So, A. M."],"bibdata":{"bibtype":"misc","type":"misc","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 {\\}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.","language":"en","urldate":"2023-07-10","publisher":"arXiv","author":[{"propositions":[],"lastnames":["Yue"],"firstnames":["Man-Chung"],"suffixes":[]},{"propositions":[],"lastnames":["So"],"firstnames":["Anthony","Man-Cho"],"suffixes":[]}],"month":"June","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","bibtex":"@misc{yue_perturbation_2014,\n\ttitle = {A {Perturbation} {Inequality} for the {Schatten}-p {Quasi}-{Norm} and {Its} {Applications} to {Low}-{Rank} {Matrix} {Recovery}},\n\turl = {http://arxiv.org/abs/1209.0377},\n\tabstract = {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.},\n\tlanguage = {en},\n\turldate = {2023-07-10},\n\tpublisher = {arXiv},\n\tauthor = {Yue, Man-Chung and So, Anthony Man-Cho},\n\tmonth = jun,\n\tyear = {2014},\n\tnote = {arXiv:1209.0377 [cs, math]},\n\tkeywords = {Computer Science - Information Theory, Mathematics - Optimization and Control},\n\tfile = {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},\n}\n","author_short":["Yue, M.","So, A. M."],"key":"yue_perturbation_2014","id":"yue_perturbation_2014","bibbaseid":"yue-so-aperturbationinequalityfortheschattenpquasinormanditsapplicationstolowrankmatrixrecovery-2014","role":"author","urls":{"Paper":"http://arxiv.org/abs/1209.0377"},"keyword":["Computer Science - Information Theory","Mathematics - Optimization and Control"],"metadata":{"authorlinks":{}},"html":""},"bibtype":"misc","biburl":"https://bibbase.org/network/files/MdCywnfEcRNyDtvne","dataSources":["yoC7aEqiuoMyGb9he"],"keywords":["computer science - information theory","mathematics - optimization and control"],"search_terms":["perturbation","inequality","schatten","quasi","norm","applications","low","rank","matrix","recovery","yue","so"],"title":"A Perturbation Inequality for the Schatten-p Quasi-Norm and Its Applications to Low-Rank Matrix Recovery","year":2014}