An Algebraic-Geometric Approach for Linear Regression Without Correspondences
Manolis Tsakiris; Liangzu Peng; Aldo Conca; Laurent Kneip; Yuanming Shi; Hayoung Choi

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 ξ* ∈ R n of the linear regression model must satisfy. This naturally leads to a polynomial system of n equations in n unknowns, which contains ξ* 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.

Indexed BySCI
Citation statistics
Cited Times:5[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Collection信息科学与技术学院_PI研究组_Manolis Tsakiris组
信息科学与技术学院_PI研究组_Laurent Kneip组
Affiliation1.ShanghaiTech University
2.ShanghaiTech University
3.University of Genova
4.ShanghaiTech University
5.ShanghaiTech University
6.ShanghaiTech University
Recommended Citation
GB/T 7714
Manolis Tsakiris,Liangzu Peng,Aldo Conca,et al. An Algebraic-Geometric Approach for Linear Regression Without Correspondences[J]. IEEE TRANSACTIONS ON INFORMATION THEORY,2020.
APA Manolis Tsakiris,Liangzu Peng,Aldo Conca,Laurent Kneip,Yuanming Shi,&Hayoung Choi.(2020).An Algebraic-Geometric Approach for Linear Regression Without Correspondences.IEEE TRANSACTIONS ON INFORMATION THEORY.
MLA Manolis Tsakiris,et al."An Algebraic-Geometric Approach for Linear Regression Without Correspondences".IEEE TRANSACTIONS ON INFORMATION THEORY (2020).
Files in This Item:
File Name/Size DocType Version Access License
1810.05440.pdf(613KB)科技报告 限制开放CC BY-NC-SAView Application Full Text
An_Algebraic-Geometr(662KB)期刊论文出版稿限制开放CC BY-NC-SAView Application Full Text
Related Services
Usage statistics
Scholar Google
Similar articles in Scholar Google
[Manolis Tsakiris]'s Articles
[Liangzu Peng]'s Articles
[Aldo Conca]'s Articles
Baidu academic
Similar articles in Baidu academic
[Manolis Tsakiris]'s Articles
[Liangzu Peng]'s Articles
[Aldo Conca]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Manolis Tsakiris]'s Articles
[Liangzu Peng]'s Articles
[Aldo Conca]'s Articles
Terms of Use
No data!
Social Bookmark/Share
File name: 1810.05440.pdf
Format: Adobe PDF
File name: An_Algebraic-Geometric_Approach_for_Linear_Regression_Without_Correspondences.pdf
Format: Adobe PDF
This file does not support browsing at this time
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.