Linear representation learning is widely studied due to its conceptual simplicity and empirical utility in tasks such as compression, classification, and feature extraction. Given a set of points $[\mathbf{ x}_1, \mathbf{ x}_2, \ldots, \mathbf{ x}_n] = \mathbf{ X} \in \mathbb{ R}^{ d \times n}$ and a vector $\mathbf{ y} \in \mathbb{ R}^d$, the goal is to find coefficients $\mathbf{ w} \in \mathbb{ R}^n$ so that $\mathbf{ X} \mathbf{ w} \approx \mathbf{ y}$, subject to some desired structure on $\mathbf{ w}$. In this work we seek $\mathbf{ w}$ that forms a local reconstruction of $\mathbf{ y}$ by solving a regularized least squares regression problem. We obtain local solutions through a locality function that promotes the use of columns of $\mathbf{ X}$ that are close to $\mathbf{ y}$ when used as a regularization term. We prove that, for all levels of regularization and under a mild condition that the columns of $\mathbf{ X}$ have a unique Delaunay triangulation, the optimal coefficients' number of non-zero entries is upper bounded by $d+1$, thereby providing local sparse solutions when $d \ll n$. Under the same condition we also show that for any $\mathbf{ y}$ contained in the convex hull of $\mathbf{ X}$ there exists a regime of regularization parameter such that the optimal coefficients are supported on the vertices of the Delaunay simplex containing $\mathbf{ y}$. This provides an interpretation of the sparsity as having structure obtained implicitly from the Delaunay triangulation of $\mathbf{ X}$. We demonstrate that our locality regularized problem can be solved in comparable time to other methods that identify the containing Delaunay simplex.

Categories: cs.LG eess.SP math.OC stat.ML

Locality Regularized Reconstruction: Structured Sparsity and Delaunay Triangulations