A Convex Optimization Approach to Robust Fundamental Matrix Estimation
This paper considers the problem of recovering a subspace arrangement from noisy samples, potentially corrupted with outliers. Our main result shows that this problem can be formulated as a constrained polynomial optimization, for which a monotonically convergent sequence of tractable convex relaxations can be obtained by exploiting recent developments in sparse polynomial optimization. Further, these results allow for deriving conditions certifying that a finite order relaxation has converged to a solution. A salient feature of the proposed approach is its ability to incorporate existing a-priori information about the noise, co-ocurrences, and percentage of outliers. These results are illustrated with several examples where the proposed algorithm is shown to outperform existing approaches.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Nonconvex Optimization Framework for Low Rank Matrix Estimation
We study the estimation of low rank matrices via nonconvex optimization. Compared with convex relaxation, nonconvex optimization exhibits superior empirical performance for large scale instances of low rank matrix estima…
Convexity in Disguise: A Theoretical Framework for Nonconvex Low-Rank Matrix Estimation
Nonconvex methods have emerged as a dominant approach for low-rank matrix estimation, a problem that arises widely in machine learning and AI for learning and representing high-dimensional data. Existing analyses for the…
A block-coordinate descent framework for non-convex composite optimization. Application to sparse precision matrix estimation
Block-coordinate descent (BCD) is the method of choice to solve numerous large scale optimization problems, however their theoretical study for non-convex optimization, has received less attention. In this paper, we pres…
Computation of the Maximum Likelihood estimator in low-rank Factor Analysis
Factor analysis, a classical multivariate statistical technique is popularly used as a fundamental tool for dimensionality reduction in statistics, econometrics and data science. Estimation is often carried out via the M…
Dimensionality ReductionEconometricsSketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
This paper concerns a fundamental class of convex matrix optimization problems. It presents the first algorithm that uses optimal storage and provably computes a low-rank approximation of a solution. In particular, when …