arXiv research

Paper shows affine constraint is unnecessary for high-dimensional data.

The Grassmannian of affine subspaces is a natural generalization of both the Euclidean space, points being zero-dimensional affine subspaces, and the usual Grassmannian, linear subspaces being special cases of affine subspaces. We show that, like the Grassmannian, the affine Grassmannian has rich geometrical and topolo…

The paper studies affine manifolds with linear foliations and their topological properties.

The affine Grassmannian is a noncompact smooth manifold that parameterizes all affine subspaces of a fixed dimension. It is a natural generalization of Euclidean space, points being zero-dimensional affine subspaces. We will realize the affine Grassmannian as a matrix manifold and extend Riemannian optimization algorit…

We present a simple and fast geometric method for modeling data by a union of affine subspaces. The method begins by forming a collection of local best-fit affine subspaces, i.e., subspaces approximating the data in local neighborhoods. The correct sizes of the local neighborhoods are determined automatically by the Jo…

The paper constructs submanifolds with corners in Delzant polytopes from affine subspaces.

Subspace clustering methods based on expressing each data point as a linear combination of all other points in a dataset are popular unsupervised learning techniques. However, existing methods incur high computational complexity on large-scale datasets as they require solving an expensive optimization problem and perfo…

Study of tangent cones at infinity for algebraic sets.

An $\varepsilon$-coreset for Least-Mean-Squares (LMS) of a matrix $A\in{\mathbb{R}}^{n\times d}$ is a small weighted subset of its rows that approximates the sum of squared distances from its rows to every affine $k$-dimensional subspace of ${\mathbb{R}}^d$, up to a factor of $1\pm\varepsilon$. Such coresets are useful…

The paper studies Anosov holonomy groups in complete affine manifolds.

Subspace clustering refers to the problem of clustering high-dimensional data into a union of low-dimensional subspaces. Current subspace clustering approaches are usually based on a two-stage framework. In the first stage, an affinity matrix is generated from data. In the second one, spectral clustering is applied on …

We consider the problem of subspace clustering: given points that lie on or near the union of many low-dimensional linear subspaces, recover the subspaces. To this end, one first identifies sets of points close to the same subspace and uses the sets to estimate the subspaces. As the geometric structure of the clusters …

PCA adapted for curved spaces improves data analysis.

State-of-the-art subspace clustering methods are based on expressing each data point as a linear combination of other data points while regularizing the matrix of coefficients with $\ell_1$, $\ell_2$ or nuclear norms. $\ell_1$ regularization is guaranteed to give a subspace-preserving affinity (i.e., there are no conne…

This paper investigates the generalization of Principal Component Analysis (PCA) to Riemannian manifolds. We first propose a new and general type of family of subspaces in manifolds that we call barycentric subspaces. They are implicitly defined as the locus of points which are weighted means of $k+1$ reference points.…

Subspace clustering is the unsupervised grouping of points lying near a union of low-dimensional linear subspaces. Algorithms based directly on geometric properties of such data tend to either provide poor empirical performance, lack theoretical guarantees, or depend heavily on their initialization. We present a novel …

Subspace clustering methods based on $\ell_1$, $\ell_2$ or nuclear norm regularization have become very popular due to their simplicity, theoretical guarantees and empirical success. However, the choice of the regularizer can greatly impact both theory and practice. For instance, $\ell_1$ regularization is guaranteed t…

We prove that if an analytic subset $A$ of a linear metric space $X$ is not contained in a $σZ_ω$-subset of $X$ then for every Polish convex set $K$ with dense affine hull in $X$ the sum $A+K$ is non-meager in $X$ and the sets $A+A+K$ and $A-A+K$ have non-empty interior in the completion $\bar X$ of $X$. This implies t…

By Markowitz geometry we mean the intersection theory of ellipsoids and affine subspaces in a real finite-dimensional linear space. In the paper we give a meticulous and self-contained treatment of this arch-classical subject, which lays a solid mathematical groundwork of Markowitz mean-variance theory of efficient por…

The problem of Hybrid Linear Modeling (HLM) is to model and segment data using a mixture of affine subspaces. Different strategies have been proposed to solve this problem, however, rigorous analysis justifying their performance is missing. This paper suggests the Theoretical Spectral Curvature Clustering (TSCC) algori…

Most existing approaches address multi-view subspace clustering problem by constructing the affinity matrix on each view separately and afterwards propose how to extend spectral clustering algorithm to handle multi-view data. This paper presents an approach to multi-view subspace clustering that learns a joint subspace…

In this article we study an exact analogue of the cross-ratio for the algebra of quaternions H and use it to derive several interesting properties of quaternionic fractional linear transformations. In particular, we show that there exists a fractional linear transformation T on H mapping four distinct quaternions q_1, …

Subspace clustering refers to the problem of clustering unlabeled high-dimensional data points into a union of low-dimensional linear subspaces, assumed unknown. In practice one may have access to dimensionality-reduced observations of the data only, resulting, e.g., from "undersampling" due to complexity and speed con…

Subspace clustering is the problem of clustering data points into a union of low-dimensional linear/affine subspaces. It is the mathematical abstraction of many important problems in computer vision, image processing and machine learning. A line of recent work (4, 19, 24, 20) provided strong theoretical guarantee for s…

Subspace clustering (SC) refers to the problem of clustering high-dimensional data into a union of low-dimensional subspaces. Based on spectral clustering, state-of-the-art approaches solve SC problem within a two-stage framework. In the first stage, data representation techniques are applied to draw an affinity matrix…

Stochastic Sparse Subspace Clustering improves subspace clustering by reducing over-segmentation through dropout.

The problem of clustering noisy and incompletely observed high-dimensional data points into a union of low-dimensional subspaces and a set of outliers is considered. The number of subspaces, their dimensions, and their orientations are assumed unknown. We propose a simple low-complexity subspace clustering algorithm, w…

For spherical Tits buildings of the classical types there are well-known explicit descriptions as flag complexes. Similarly for affine buildings of the classical types there are explicit constructions in terms of lattices. In this article we generalize the flag complex description to twin cities, a generalization of tw…

A robust visual tracking system requires an object appearance model that is able to handle occlusion, pose, and illumination variations in the video stream. This can be difficult to accomplish when the model is trained using only a single image. In this paper, we first propose a tracking approach based on affine subspa…

The study limits the cohomological dimension of certain affine manifolds with partially hyperbolic holonomy groups.

New method learns subspace affinity function for scalable and inductive clustering.

Multi-view subspace clustering has been applied to applications such as image processing and video surveillance, and has attracted increasing attention. Most existing methods learn view-specific self-representation matrices, and construct a combined affinity matrix from multiple views. The affinity construction process…

Study closed manifolds with rank one ray structures, proving completeness or covering properties.

DKLM learns adaptive kernels for robust nonlinear subspace clustering.

We consider a generalization of low-rank matrix completion to the case where the data belongs to an algebraic variety, i.e. each data point is a solution to a system of polynomial equations. In this case the original matrix is possibly high-rank, but it becomes low-rank after mapping each column to a higher dimensional…

Extends Kähler metrics theory to symplectic manifolds with toric actions.

We consider the problem of clustering noisy high-dimensional data points into a union of low-dimensional subspaces and a set of outliers. The number of subspaces, their dimensions, and their orientations are unknown. A probabilistic performance analysis of the thresholding-based subspace clustering (TSC) algorithm intr…

Consider a closed connected hypersurface in $\mathbb{R}^n$ with constant signature (k,l) of the second quadratic form, and approaching a quadratic cone at infinity. This hypersurface divides $\mathbb{R}^n$ into two pieces. We prove that one of them contains a k-dimensional subspace, and another contains a l-dimensional…

We describe pairs (p,n) such that n-dimensional affine space is fibered by pairwise skew p-dimensional affine subspaces. The problem is closely related with the theorem of Adams on vector fields on spheres and the Hurwitz-Radon theory of composition of quadratic forms.

Subspace segmentation assumes that data comes from the union of different subspaces and the purpose of segmentation is to partition the data into the corresponding subspace. Low-rank representation (LRR) is a classic spectral-type method for solving subspace segmentation problems, that is, one first obtains an affinity…

Researchers describe Casimir functions for 3- and 4-step nilpotent Lie groups.

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…

Bicycle paths form geodesics in 3D subspaces, related to Kirchhoff rods.

We describe the fundamental groups of ordered and unordered $k-$point sets in the n-dimensional complex space $C^n$ generating an affine subspace of fixed dimension.

Paper proves IRLS converges to subspace from any start, with practical benefits.

Meta-learning bandits by reducing dimensionality with PCA.

Reconstruction based subspace clustering methods compute a self reconstruction matrix over the samples and use it for spectral clustering to obtain the final clustering result. Their success largely relies on the assumption that the underlying subspaces are independent, which, however, does not always hold in the appli…

We describe the Fast Greedy Sparse Subspace Clustering (FGSSC) algorithm providing an efficient method for clustering data belonging to a few low-dimensional linear or affine subspaces. The main difference of our algorithm from predecessors is its ability to work with noisy data having a high rate of erasures (missed e…