Please use this identifier to cite or link to this item: http://localhost/handle/Hannan/588436
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBo Xinen_US
dc.contributor.authorYizhou Wangen_US
dc.contributor.authorWen Gaoen_US
dc.contributor.authorDavid Wipfen_US
dc.date.accessioned2020-05-20T08:39:00Z-
dc.date.available2020-05-20T08:39:00Z-
dc.date.issued2016en_US
dc.identifier.issn1053-587Xen_US
dc.identifier.issn1941-0476en_US
dc.identifier.other10.1109/TSP.2016.2551697en_US
dc.identifier.urihttp://localhost/handle/Hannan/172583en_US
dc.identifier.urihttp://localhost/handle/Hannan/588436-
dc.description.abstractMany 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.en_US
dc.publisherIEEEen_US
dc.relation.haspart7448979.pdfen_US
dc.subjectRank minimization|empirical Bayes|matrix recovery|affine constraints|matrix completionen_US
dc.titleExploring Algorithmic Limits of Matrix Rank Minimization Under Affine Constraintsen_US
dc.typeArticleen_US
dc.journal.volume64en_US
dc.journal.issue19en_US
dc.journal.titleIEEE Transactions on Signal Processingen_US
Appears in Collections:2016

Files in This Item:
File Description SizeFormat 
7448979.pdf1.18 MBAdobe PDFThumbnail
Preview File
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBo Xinen_US
dc.contributor.authorYizhou Wangen_US
dc.contributor.authorWen Gaoen_US
dc.contributor.authorDavid Wipfen_US
dc.date.accessioned2020-05-20T08:39:00Z-
dc.date.available2020-05-20T08:39:00Z-
dc.date.issued2016en_US
dc.identifier.issn1053-587Xen_US
dc.identifier.issn1941-0476en_US
dc.identifier.other10.1109/TSP.2016.2551697en_US
dc.identifier.urihttp://localhost/handle/Hannan/172583en_US
dc.identifier.urihttp://localhost/handle/Hannan/588436-
dc.description.abstractMany 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.en_US
dc.publisherIEEEen_US
dc.relation.haspart7448979.pdfen_US
dc.subjectRank minimization|empirical Bayes|matrix recovery|affine constraints|matrix completionen_US
dc.titleExploring Algorithmic Limits of Matrix Rank Minimization Under Affine Constraintsen_US
dc.typeArticleen_US
dc.journal.volume64en_US
dc.journal.issue19en_US
dc.journal.titleIEEE Transactions on Signal Processingen_US
Appears in Collections:2016

Files in This Item:
File Description SizeFormat 
7448979.pdf1.18 MBAdobe PDFThumbnail
Preview File
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBo Xinen_US
dc.contributor.authorYizhou Wangen_US
dc.contributor.authorWen Gaoen_US
dc.contributor.authorDavid Wipfen_US
dc.date.accessioned2020-05-20T08:39:00Z-
dc.date.available2020-05-20T08:39:00Z-
dc.date.issued2016en_US
dc.identifier.issn1053-587Xen_US
dc.identifier.issn1941-0476en_US
dc.identifier.other10.1109/TSP.2016.2551697en_US
dc.identifier.urihttp://localhost/handle/Hannan/172583en_US
dc.identifier.urihttp://localhost/handle/Hannan/588436-
dc.description.abstractMany 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.en_US
dc.publisherIEEEen_US
dc.relation.haspart7448979.pdfen_US
dc.subjectRank minimization|empirical Bayes|matrix recovery|affine constraints|matrix completionen_US
dc.titleExploring Algorithmic Limits of Matrix Rank Minimization Under Affine Constraintsen_US
dc.typeArticleen_US
dc.journal.volume64en_US
dc.journal.issue19en_US
dc.journal.titleIEEE Transactions on Signal Processingen_US
Appears in Collections:2016

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