@misc{bach-arxiv13,
	title = {Convex relaxations of structured matrix factorizations},
	url = {http://arxiv.org/abs/1309.3117},
	abstract = {We consider the factorization of a rectangular matrix \$X \$ into a positive linear combination of rank-one factors of the form \$u v{\textasciicircum}{\textbackslash}top\$, where \$u\$ and \$v\$ belongs to certain sets \${\textbackslash}mathcal\{U\}\$ and \${\textbackslash}mathcal\{V\}\$, that may encode specific structures regarding the factors, such as positivity or sparsity. In this paper, we show that computing the optimal decomposition is equivalent to computing a certain gauge function of \$X\$ and we provide a detailed analysis of these gauge functions and their polars. Since these gauge functions are typically hard to compute, we present semi-definite relaxations and several algorithms that may recover approximate decompositions with approximation guarantees. We illustrate our results with simulations on finding decompositions with elements in \${\textbackslash}\{0,1{\textbackslash}\}\$. As side contributions, we present a detailed analysis of variational quadratic representations of norms as well as a new iterative basis pursuit algorithm that can deal with inexact first-order oracles.},
	number = {{arXiv}:1309.3117},
	publisher = {{arXiv}},
	author = {Bach, Francis},
	urldate = {2024-01-16},
	date = {2013-09-12},
	eprinttype = {arxiv},
	eprint = {1309.3117 [cs, math]},
	keywords = {Computer Science - Machine Learning, Mathematics - Optimization and Control},
	file = {arXiv.org Snapshot:/Users/ukreddy/Zotero/storage/BWLAY4CW/1309.html:text/html;Full Text PDF:/Users/ukreddy/Zotero/storage/34TL4VEA/Bach - 2013 - Convex relaxations of structured matrix factorizat.pdf:application/pdf},
}

{"_id":"Z7SgvCFDikzkTNAhp","bibbaseid":"bach-convexrelaxationsofstructuredmatrixfactorizations","author_short":["Bach, F."],"bibdata":{"bibtype":"misc","type":"misc","title":"Convex relaxations of structured matrix factorizations","url":"http://arxiv.org/abs/1309.3117","abstract":"We consider the factorization of a rectangular matrix $X $ into a positive linear combination of rank-one factors of the form $u v{\\textasciicircum}{\\}top$, where $u$ and $v$ belongs to certain sets ${\\}mathcal\\{U\\}$ and ${\\}mathcal\\{V\\}$, that may encode specific structures regarding the factors, such as positivity or sparsity. In this paper, we show that computing the optimal decomposition is equivalent to computing a certain gauge function of $X$ and we provide a detailed analysis of these gauge functions and their polars. Since these gauge functions are typically hard to compute, we present semi-definite relaxations and several algorithms that may recover approximate decompositions with approximation guarantees. We illustrate our results with simulations on finding decompositions with elements in ${\\}\\{0,1{\\}\\}$. As side contributions, we present a detailed analysis of variational quadratic representations of norms as well as a new iterative basis pursuit algorithm that can deal with inexact first-order oracles.","number":"arXiv:1309.3117","publisher":"arXiv","author":[{"propositions":[],"lastnames":["Bach"],"firstnames":["Francis"],"suffixes":[]}],"urldate":"2024-01-16","date":"2013-09-12","eprinttype":"arxiv","eprint":"1309.3117 [cs, math]","keywords":"Computer Science - Machine Learning, Mathematics - Optimization and Control","file":"arXiv.org Snapshot:/Users/ukreddy/Zotero/storage/BWLAY4CW/1309.html:text/html;Full Text PDF:/Users/ukreddy/Zotero/storage/34TL4VEA/Bach - 2013 - Convex relaxations of structured matrix factorizat.pdf:application/pdf","bibtex":"@misc{bach-arxiv13,\n\ttitle = {Convex relaxations of structured matrix factorizations},\n\turl = {http://arxiv.org/abs/1309.3117},\n\tabstract = {We consider the factorization of a rectangular matrix \\$X \\$ into a positive linear combination of rank-one factors of the form \\$u v{\\textasciicircum}{\\textbackslash}top\\$, where \\$u\\$ and \\$v\\$ belongs to certain sets \\${\\textbackslash}mathcal\\{U\\}\\$ and \\${\\textbackslash}mathcal\\{V\\}\\$, that may encode specific structures regarding the factors, such as positivity or sparsity. In this paper, we show that computing the optimal decomposition is equivalent to computing a certain gauge function of \\$X\\$ and we provide a detailed analysis of these gauge functions and their polars. Since these gauge functions are typically hard to compute, we present semi-definite relaxations and several algorithms that may recover approximate decompositions with approximation guarantees. We illustrate our results with simulations on finding decompositions with elements in \\${\\textbackslash}\\{0,1{\\textbackslash}\\}\\$. As side contributions, we present a detailed analysis of variational quadratic representations of norms as well as a new iterative basis pursuit algorithm that can deal with inexact first-order oracles.},\n\tnumber = {{arXiv}:1309.3117},\n\tpublisher = {{arXiv}},\n\tauthor = {Bach, Francis},\n\turldate = {2024-01-16},\n\tdate = {2013-09-12},\n\teprinttype = {arxiv},\n\teprint = {1309.3117 [cs, math]},\n\tkeywords = {Computer Science - Machine Learning, Mathematics - Optimization and Control},\n\tfile = {arXiv.org Snapshot:/Users/ukreddy/Zotero/storage/BWLAY4CW/1309.html:text/html;Full Text PDF:/Users/ukreddy/Zotero/storage/34TL4VEA/Bach - 2013 - Convex relaxations of structured matrix factorizat.pdf:application/pdf},\n}\n\n\n","author_short":["Bach, F."],"key":"bach-arxiv13","id":"bach-arxiv13","bibbaseid":"bach-convexrelaxationsofstructuredmatrixfactorizations","role":"author","urls":{"Paper":"http://arxiv.org/abs/1309.3117"},"keyword":["Computer Science - Machine Learning","Mathematics - Optimization and Control"],"metadata":{"authorlinks":{}},"downloads":0,"html":""},"bibtype":"misc","biburl":"https://bibbase.org/network/files/ERQPGxTT5rBCWeLFE","dataSources":["TJKHZ3TN7ogruuAa6"],"keywords":["computer science - machine learning","mathematics - optimization and control"],"search_terms":["convex","relaxations","structured","matrix","factorizations","bach"],"title":"Convex relaxations of structured matrix factorizations","year":null}