Symmetry-free SDP Relaxations for Affine Subspace Clustering
We consider clustering problems where the goal is to determine an optimal partition of a given point set in Euclidean space in terms of a collection of affine subspaces. While there is vast literature on heuristics for this kind of problem, such approaches are known to be susceptible to poor initializations and getting trapped in bad local optima. We alleviate these issues by introducing a semidefinite relaxation based on Lasserre's method of moments. While a similiar approach is known for classical Euclidean clustering problems, a generalization to our more general subspace scenario is not straightforward, due to the high symmetry of the objective function that weakens any convex relaxation. We therefore introduce a new mechanism for symmetry breaking based on covering the feasible region with polytopes. Additionally, we introduce and analyze a deterministic rounding heuristic.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Is an Affine Constraint Needed for Affine Subspace Clustering?
Subspace clustering methods based on expressing each data point as a linear combination of other data points have achieved great success in computer vision applications such as motion segmentation, face and digit cluster…
ClusteringFace ClusteringMotion SegmentationAlgebraic Clustering of Affine Subspaces
Subspace clustering is an important problem in machine learning with many applications in computer vision and pattern recognition. Prior work has studied this problem using algebraic, iterative, statistical, low-rank and…
ClusteringPositionOn Geometric Analysis of Affine Sparse Subspace Clustering
Sparse subspace clustering (SSC) is a state-of-the-art method for segmenting a set of data points drawn from a union of subspaces into their respective subspaces. It is now well understood that SSC produces subspace-pres…
ClusteringAffine Subspace Models and Clustering for Patch-Based Image Denoising
Image tile-based approaches are popular in many image processing applications such as denoising (e.g., non-local means). A key step in their use is grouping the images into clusters, which usually proceeds iteratively sp…
Image DenoisingGeometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances
We study how permutation symmetries in overparameterized multi-layer neural networks generate `symmetry-induced' critical points. Assuming a network with $ L $ layers of minimal widths $ r_1^*, \ldots, r_{L-1}^* $ reache…