An Algebraic-Geometric Approach for Linear Regression Without Correspondences.
Saved in:
| Title: | An Algebraic-Geometric Approach for Linear Regression Without Correspondences. |
|---|---|
| Authors: | Tsakiris, Manolis C.1 mtsakiris@shanghaitech.edu.cn, Peng, Liangzu1, Conca, Aldo2, Kneip, Laurent1, Shi, Yuanming1, Choi, Hayoung1 |
| Source: | IEEE Transactions on Information Theory. Aug2020, Vol. 66 Issue 8, p5130-5144. 15p. |
| Subjects: | Algebraic geometry, Linear equations, Algorithms, Data corruption, Geometric approach, Linear systems |
| Abstract: | Linear regression without correspondences is the problem of performing a linear regression fit to a dataset for which the correspondences between the independent samples and the observations are unknown. Such a problem naturally arises in diverse domains such as computer vision, data mining, communications and biology. In its simplest form, it is tantamount to solving a linear system of equations, for which the entries of the right hand side vector have been permuted. This type of data corruption renders the linear regression task considerably harder, even in the absence of other corruptions, such as noise, outliers or missing entries. Existing methods are either applicable only to noiseless data or they are very sensitive to initialization or they work only for partially shuffled data. In this paper we address these issues via an algebraic geometric approach, which uses symmetric polynomials to extract permutation-invariant constraints that the parameters $\xi ^{*} \in \mathbb {R} ^{\text {n}}$ of the linear regression model must satisfy. This naturally leads to a polynomial system of n equations in n unknowns, which contains $\xi ^{*}$ in its root locus. Using the machinery of algebraic geometry we prove that as long as the independent samples are generic, this polynomial system is always consistent with at most n! complex roots, regardless of any type of corruption inflicted on the observations. The algorithmic implication of this fact is that one can always solve this polynomial system and use its most suitable root as initialization to the Expectation Maximization algorithm. To the best of our knowledge, the resulting method is the first working solution for small values of n able to handle thousands of fully shuffled noisy observations in milliseconds. [ABSTRACT FROM AUTHOR] |
| Copyright of IEEE Transactions on Information Theory is the property of IEEE 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: 144615694 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: An Algebraic-Geometric Approach for Linear Regression Without Correspondences. – 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="%22Peng%2C+Liangzu%22">Peng, Liangzu</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Conca%2C+Aldo%22">Conca, Aldo</searchLink><relatesTo>2</relatesTo><br /><searchLink fieldCode="AR" term="%22Kneip%2C+Laurent%22">Kneip, Laurent</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Shi%2C+Yuanming%22">Shi, Yuanming</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Choi%2C+Hayoung%22">Choi, Hayoung</searchLink><relatesTo>1</relatesTo> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Information+Theory%22">IEEE Transactions on Information Theory</searchLink>. Aug2020, Vol. 66 Issue 8, p5130-5144. 15p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Algebraic+geometry%22">Algebraic geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+equations%22">Linear equations</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Data+corruption%22">Data corruption</searchLink><br /><searchLink fieldCode="DE" term="%22Geometric+approach%22">Geometric approach</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+systems%22">Linear systems</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Linear regression without correspondences is the problem of performing a linear regression fit to a dataset for which the correspondences between the independent samples and the observations are unknown. Such a problem naturally arises in diverse domains such as computer vision, data mining, communications and biology. In its simplest form, it is tantamount to solving a linear system of equations, for which the entries of the right hand side vector have been permuted. This type of data corruption renders the linear regression task considerably harder, even in the absence of other corruptions, such as noise, outliers or missing entries. Existing methods are either applicable only to noiseless data or they are very sensitive to initialization or they work only for partially shuffled data. In this paper we address these issues via an algebraic geometric approach, which uses symmetric polynomials to extract permutation-invariant constraints that the parameters $\xi ^{*} \in \mathbb {R} ^{\text {n}}$ of the linear regression model must satisfy. This naturally leads to a polynomial system of n equations in n unknowns, which contains $\xi ^{*}$ in its root locus. Using the machinery of algebraic geometry we prove that as long as the independent samples are generic, this polynomial system is always consistent with at most n! complex roots, regardless of any type of corruption inflicted on the observations. The algorithmic implication of this fact is that one can always solve this polynomial system and use its most suitable root as initialization to the Expectation Maximization algorithm. To the best of our knowledge, the resulting method is the first working solution for small values of n able to handle thousands of fully shuffled noisy observations in milliseconds. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of IEEE Transactions on Information Theory is the property of IEEE 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=144615694 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1109/TIT.2020.2977166 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 15 StartPage: 5130 Subjects: – SubjectFull: Algebraic geometry Type: general – SubjectFull: Linear equations Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Data corruption Type: general – SubjectFull: Geometric approach Type: general – SubjectFull: Linear systems Type: general Titles: – TitleFull: An Algebraic-Geometric Approach for Linear Regression Without Correspondences. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Tsakiris, Manolis C. – PersonEntity: Name: NameFull: Peng, Liangzu – PersonEntity: Name: NameFull: Conca, Aldo – PersonEntity: Name: NameFull: Kneip, Laurent – PersonEntity: Name: NameFull: Shi, Yuanming – PersonEntity: Name: NameFull: Choi, Hayoung IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 08 Text: Aug2020 Type: published Y: 2020 Identifiers: – Type: issn-print Value: 00189448 Numbering: – Type: volume Value: 66 – Type: issue Value: 8 Titles: – TitleFull: IEEE Transactions on Information Theory Type: main |
| ResultId | 1 |
