Dual Principal Component Pursuit.
Saved in:
| Title: | Dual Principal Component Pursuit. |
|---|---|
| Authors: | Tsakiris, Manolis C.1 MTSAKIRIS@SHANGHAITECH.EDU.CN, Vidal, René2 RVIDAL@JHU.EDU |
| Source: | Journal of Machine Learning Research. 2018, Vol. 19 Issue 1-26, p1-49. 49p. |
| Subjects: | Information science, Subspaces (Mathematics), Learning ability, Algorithms, Data analysis, Problem solving |
| Abstract: | We consider the problem of learning a linear subspace from data corrupted by outliers. Classical approaches are typically designed for the case in which the subspace dimension is small relative to the ambient dimension. Our approach works with a dual representation of the subspace and hence aims to find its orthogonal complement; as such, it is particularly suitable for subspaces whose dimension is close to the ambient dimension (subspaces of high relative dimension). We pose the problem of computing normal vectors to the inlier subspace as a non-convex ℓ1 minimization problem on the sphere, which we call Dual Principal Component Pursuit (DPCP) problem. We provide theoretical guarantees under which every global solution to DPCP is a vector in the orthogonal complement of the inlier subspace. Moreover, we relax the non-convex DPCP problem to a recursion of linear programs whose solutions are shown to converge in a finite number of steps to a vector orthogonal to the subspace. In particular, when the inlier subspace is a hyperplane, the solutions to the recursion of linear programs converge to the global minimum of the non-convex DPCP problem in a finite number of steps. We also propose algorithms based on alternating minimization and iteratively re-weighted least squares, which are suitable for dealing with large-scale data. Experiments on synthetic data show that the proposed methods are able to handle more outliers and higher relative dimensions than current state-of-the-art methods, while experiments in the context of the three-view geometry problem in computer vision suggest that the proposed methods can be a useful or even superior alternative to traditional RANSAC-based approaches for computer vision and other applications. [ABSTRACT FROM AUTHOR] |
| Copyright of Journal of Machine Learning Research is the property of Microtome Publishing and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 131718069 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Dual Principal Component Pursuit. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Tsakiris%2C+Manolis+C%2E%22">Tsakiris, Manolis C.</searchLink><relatesTo>1</relatesTo><i> MTSAKIRIS@SHANGHAITECH.EDU.CN</i><br /><searchLink fieldCode="AR" term="%22Vidal%2C+René%22">Vidal, René</searchLink><relatesTo>2</relatesTo><i> RVIDAL@JHU.EDU</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Journal+of+Machine+Learning+Research%22">Journal of Machine Learning Research</searchLink>. 2018, Vol. 19 Issue 1-26, p1-49. 49p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Information+science%22">Information science</searchLink><br /><searchLink fieldCode="DE" term="%22Subspaces+%28Mathematics%29%22">Subspaces (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Learning+ability%22">Learning ability</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Data+analysis%22">Data analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Problem+solving%22">Problem solving</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: We consider the problem of learning a linear subspace from data corrupted by outliers. Classical approaches are typically designed for the case in which the subspace dimension is small relative to the ambient dimension. Our approach works with a dual representation of the subspace and hence aims to find its orthogonal complement; as such, it is particularly suitable for subspaces whose dimension is close to the ambient dimension (subspaces of high relative dimension). We pose the problem of computing normal vectors to the inlier subspace as a non-convex ℓ1 minimization problem on the sphere, which we call Dual Principal Component Pursuit (DPCP) problem. We provide theoretical guarantees under which every global solution to DPCP is a vector in the orthogonal complement of the inlier subspace. Moreover, we relax the non-convex DPCP problem to a recursion of linear programs whose solutions are shown to converge in a finite number of steps to a vector orthogonal to the subspace. In particular, when the inlier subspace is a hyperplane, the solutions to the recursion of linear programs converge to the global minimum of the non-convex DPCP problem in a finite number of steps. We also propose algorithms based on alternating minimization and iteratively re-weighted least squares, which are suitable for dealing with large-scale data. Experiments on synthetic data show that the proposed methods are able to handle more outliers and higher relative dimensions than current state-of-the-art methods, while experiments in the context of the three-view geometry problem in computer vision suggest that the proposed methods can be a useful or even superior alternative to traditional RANSAC-based approaches for computer vision and other applications. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Journal of Machine Learning Research is the property of Microtome Publishing and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=131718069 |
| RecordInfo | BibRecord: BibEntity: Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 49 StartPage: 1 Subjects: – SubjectFull: Information science Type: general – SubjectFull: Subspaces (Mathematics) Type: general – SubjectFull: Learning ability Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Data analysis Type: general – SubjectFull: Problem solving Type: general Titles: – TitleFull: Dual Principal Component Pursuit. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Tsakiris, Manolis C. – PersonEntity: Name: NameFull: Vidal, René IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 09 Text: 2018 Type: published Y: 2018 Identifiers: – Type: issn-print Value: 15324435 Numbering: – Type: volume Value: 19 – Type: issue Value: 1-26 Titles: – TitleFull: Journal of Machine Learning Research Type: main |
| ResultId | 1 |
