Please use this identifier to cite or link to this item: http://localhost/handle/Hannan/588436
Title: Exploring Algorithmic Limits of Matrix Rank Minimization Under Affine Constraints
Authors: Bo Xin;Yizhou Wang;Wen Gao;David Wipf
subject: Rank minimization|empirical Bayes|matrix recovery|affine constraints|matrix completion
Year: 2016
Publisher: IEEE
Abstract: Many applications require recovering a matrix of minimal rank within an affine constraint set, with matrix completion a notable special case. Because the problem is NP-hard in general, it is common to replace the matrix rank with the nuclear norm, which acts as a convenient convex surrogate. While elegant theoretical conditions elucidate when this replacement is likely to be successful, they are highly restrictive and convex algorithms fail when the ambient rank is too high or when the constraint set is poorly structured. Nonconvex alternatives fare somewhat better when carefully tuned; however, convergence to locally optimal solutions remains a continuing source of failure. Against this backdrop, we derive a deceptively simple and parameter-free probabilistic PCA-like algorithm that is capable, over a wide battery of empirical tests, of successful recovery even at the theoretical limit where the number of measurements equals the degrees of freedom in the unknown low-rank matrix. Somewhat surprisingly, this is possible even when the affine constraint set is highly ill-conditioned. While proving general recovery guarantees remains evasive for nonconvex algorithms, Bayesian-inspired or otherwise, we nonetheless show conditions whereby the underlying cost function has a unique stationary point located at the global optimum; no existing cost function we are aware of satisfies this property. The algorithm has also been successfully deployed on a computer vision application involving image rectification and a standard collaborative filtering benchmark.
URI: http://localhost/handle/Hannan/172583
http://localhost/handle/Hannan/588436
ISSN: 1053-587X
1941-0476
volume: 64
issue: 19
Appears in Collections:2016

Files in This Item:
File Description SizeFormat 
7448979.pdf1.18 MBAdobe PDFThumbnail
Preview File
Title: Exploring Algorithmic Limits of Matrix Rank Minimization Under Affine Constraints
Authors: Bo Xin;Yizhou Wang;Wen Gao;David Wipf
subject: Rank minimization|empirical Bayes|matrix recovery|affine constraints|matrix completion
Year: 2016
Publisher: IEEE
Abstract: Many applications require recovering a matrix of minimal rank within an affine constraint set, with matrix completion a notable special case. Because the problem is NP-hard in general, it is common to replace the matrix rank with the nuclear norm, which acts as a convenient convex surrogate. While elegant theoretical conditions elucidate when this replacement is likely to be successful, they are highly restrictive and convex algorithms fail when the ambient rank is too high or when the constraint set is poorly structured. Nonconvex alternatives fare somewhat better when carefully tuned; however, convergence to locally optimal solutions remains a continuing source of failure. Against this backdrop, we derive a deceptively simple and parameter-free probabilistic PCA-like algorithm that is capable, over a wide battery of empirical tests, of successful recovery even at the theoretical limit where the number of measurements equals the degrees of freedom in the unknown low-rank matrix. Somewhat surprisingly, this is possible even when the affine constraint set is highly ill-conditioned. While proving general recovery guarantees remains evasive for nonconvex algorithms, Bayesian-inspired or otherwise, we nonetheless show conditions whereby the underlying cost function has a unique stationary point located at the global optimum; no existing cost function we are aware of satisfies this property. The algorithm has also been successfully deployed on a computer vision application involving image rectification and a standard collaborative filtering benchmark.
URI: http://localhost/handle/Hannan/172583
http://localhost/handle/Hannan/588436
ISSN: 1053-587X
1941-0476
volume: 64
issue: 19
Appears in Collections:2016

Files in This Item:
File Description SizeFormat 
7448979.pdf1.18 MBAdobe PDFThumbnail
Preview File
Title: Exploring Algorithmic Limits of Matrix Rank Minimization Under Affine Constraints
Authors: Bo Xin;Yizhou Wang;Wen Gao;David Wipf
subject: Rank minimization|empirical Bayes|matrix recovery|affine constraints|matrix completion
Year: 2016
Publisher: IEEE
Abstract: Many applications require recovering a matrix of minimal rank within an affine constraint set, with matrix completion a notable special case. Because the problem is NP-hard in general, it is common to replace the matrix rank with the nuclear norm, which acts as a convenient convex surrogate. While elegant theoretical conditions elucidate when this replacement is likely to be successful, they are highly restrictive and convex algorithms fail when the ambient rank is too high or when the constraint set is poorly structured. Nonconvex alternatives fare somewhat better when carefully tuned; however, convergence to locally optimal solutions remains a continuing source of failure. Against this backdrop, we derive a deceptively simple and parameter-free probabilistic PCA-like algorithm that is capable, over a wide battery of empirical tests, of successful recovery even at the theoretical limit where the number of measurements equals the degrees of freedom in the unknown low-rank matrix. Somewhat surprisingly, this is possible even when the affine constraint set is highly ill-conditioned. While proving general recovery guarantees remains evasive for nonconvex algorithms, Bayesian-inspired or otherwise, we nonetheless show conditions whereby the underlying cost function has a unique stationary point located at the global optimum; no existing cost function we are aware of satisfies this property. The algorithm has also been successfully deployed on a computer vision application involving image rectification and a standard collaborative filtering benchmark.
URI: http://localhost/handle/Hannan/172583
http://localhost/handle/Hannan/588436
ISSN: 1053-587X
1941-0476
volume: 64
issue: 19
Appears in Collections:2016

Files in This Item:
File Description SizeFormat 
7448979.pdf1.18 MBAdobe PDFThumbnail
Preview File