An Incremental Non-Linear Manifold Approximation Method

Praveen T. W. Hettige, Benjamin W. Ong · 2025

Read An Incremental Non-Linear Manifold Approximation Method by Praveen T. W. Hettige, Benjamin W. Ong (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-09068.txt.

Introduction

Hettige and Ong present a method for shrinking complex data while it streams in, in a 2025 paper. High-dimensional data is costly to store and draw, and curved patterns defeat straight-line shortcuts. Their method builds on a multi-scale framework that maps data clusters at several levels of detail at once.

Instead of rebuilding the map for each new batch, the method updates the cluster map, the local axes, and the detail coefficients step by step. Tests show the live map stays close to one built from all data at once, even when it starts from a small sample. The multi-level structure survives the updates. The authors aim the tool at live displays and graphics tools that must react as data arrives.

Catalog record

CREATORPraveen T. W. Hettige, Benjamin W. Ong
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-09068

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Incremental Non-Linear Manifold Approximation Method Praveen T. W. Hettige, Benjamin W. Ong Abstract Analyzing high-dimensional data presents challenges due to the “curse of dimensionality”, making computations intensive. Dimension reduction techniques, categorized as linear or non-linear, simplify such data. Non-linear methods are particularly essential for efficiently visualizing and processing complex data structures in interactive and graphical applications. This research develops an incremental non-linear dimension reduction method using the Geometric Multi-Resolution Analysis (GMRA) framework for streaming data. The proposed method enables real-time data analysis and visualization by incrementally updating the cluster map, PCA basis vectors, and wavelet coefficients. Numerical experiments show that the incremental GMRA accurately represents non-linear manifolds even with small initial samples and aligns closely with batch GMRA, demonstrating efficient updates and maintaining the multiscale structure. The findings highlight the potential of Incremental GMRA for real-time visualization and interactive graphics applications that require adaptive high-dimensional data representations. Keywords Incremental, Manifold Learning, Multiscale, Non-linear 1 Introduction High-dimensional data analysis often faces the challenge of the “curse of dimensionality”. This refers to the difficulty and expense of analyzing data with many parameters and features. Fortunately, high-dimensional data frequently exhibits redundancy or interdependence between parameters and/or features. Dimensionality reduction techniques are valuable tools to capture this redundancy and simplify complex data into a more manageable form. These techniques, broadly categorized as linear and non-linear, are crucial for data visualization, feature extraction. Linear dimension reduction methods such as Principal Component Analysis (PCA) [ 1 ] efficiently project high-dimensional data onto a hyperplane, a lower-dimensional subspace (a hyperplane). However, in practice, many data sets are distributed along non-linear manifolds. Non-linear dimension reduction (NLDR) achieves a similar goal as linear dimension reduction methods but projects high-dimensional data into a non-linear lower-dimensional subspace. NLDR techniques offer valuable capabilities for visualizing complex data sets, reducing the noise in data, identifying clusters, or as an intermediate step within other analysis techniques for general data sets. There are several popular NLDR techniques, e.g., Kernel PCA [ 2 ] , Laplacian Eigenmaps [ 3 ] , locally-linear embedding [ 4 ] , and t-SNE [ 5 ] , among others. Geometric Multi-resolution Analysis (GMRA) [ 6 ] is a novel method of identifying non-linear low-dimensional manifolds and representing data efficiently. Most NLDR techniques were originally designed for static batch data. However, the increasing need for real-time visualization and interactive graphics applications has led to the demand for NLDR methods capable of handling streaming data. Several NLDR methods have been extended for streaming data dimension reduction. Although GMRA has been applied in streaming data scenarios such as anomaly detection in solar flares [ 7 ] and hyperspectral image anomaly detection [ 8 ] , no specific algorithm has been proposed to address its application for handling streaming data and addressing potential challenges. This paper proposes a streaming NLDR algorithm based on GMRA for approximating non-linear manifolds. In addition, it explores the challenges associated with using GMRA in the context of streaming data. 2 GMRA Geometric multi-resolution analysis (GMRA) [ 6 ] is a somewhat recent method for identifying non-linear low-dimensional manifolds. The idea is as follows. Suppose that one uses PCA to construct a low-dimensional affine plane to approximate the data. GMRA measures the residual that arises from the affine plane approximation, and if necessary, partitions and computes a correction to the (root-level) affine plane for each partition using the residuals. The combination of the PCA (root-level) affine plane and the (finer-scale) correction gives rise to two-level approximation to the manifold, which can be visualized as a union of affine planes. Iterating this process provides a multi-scale approximation to the manifold. The GMRA framework is particularly attractive because it is data-adaptive, with the ability to generate a non-linear manifold approximation without over- or under-fitting the data based on residual estimates. Then, a fast transform algorithm is able to map data to the low-dimensional manifold which can be used in applications such as classification or regression. Figure 1 shows an illustrative example figure of GMRA construction. We proceed with a description of the GMRA algorithm and supporting theoretical analysis. Figure 1: An example illustration of a tree decomposition of point cloud data and hyperplane approximations at each tree node. At the root level, all the sample points are contained within a single node. At the second level, the samples split into two nodes, and the leaf level comprises five tree nodes. Each tree node is represented in a different color. The construction of this GMRA sketch begins with a nested multiscale decomposition of the data X=\{\vec{x}_{1},\cdots,\vec{x}_{N}\}\subset\mathbb{R}^{D} into a tree structure. We utilize a covertree structure [ 9 ] , which gives rise to partitions that satisfy assumptions for the error estimates. Each tree node corresponds to a nested subset of the data, C_{s,p}\subseteq X , that is indexed by both scale s , and relative spatial position p . The depth of the tree node corresponds directly with scale: the tree root at s=1 corresponds to the entire dataset, C_{1,1}:=X , at the scale of the diameter of X (i.e., at the coarsest data scale), and each child of a given tree node always corresponds to a subset of the parent’s subset (i.e., each C_{s,p}\subset C_{s-1,p^{\prime}} for some p^{\prime} ). Furthermore, the diameter of each child C_{s,p} is required to be at most a fraction (e.g., one half) of the diameter of its parent C_{s-1,p^{\prime}} unless the parent simply replicates itself at the next scale (i.e., unless C_{s,p}=C_{s-1,p^{\prime}} ). It is this last requirement that enforces the general correspondence between depth in the tree, and spatial scale. Finally, for any fixed scale s , \{C_{s,1},\dots,C_{s,P_{s}}\} forms a partition of the dataset X . Then, the following components are computed for each tree node of the GMRA approximation: 1. A center, \vec{c}_{s,p}\in\mathbb{R}^{D} , that represents the general spatial position of the data in C_{s,p} . 2. An orthogonal geometric scaling matrix, \Phi_{s,p}\in\mathbb{R}^{D\times d} , whose columns span a d -dimensional linear approximation to the re-centered data, (C_{s,p}-\vec{c}_{s,p}) . 3. A wavelet constant for C_{s,p} defined by w_{s,p}:=\left(I-\Phi_{s-1,p^{\prime}}\Phi^{T}_{s-1,p^{\prime}}\right)\cdot(\vec{c}_{s,p}-\vec{c}_{s-1,p^{\prime}})\in\mathbb{R}^{D}, where C_{s-1,p^{\prime}} is the parent subset containing C_{s,p} , and an orthogonal wavelet basis matrix, \Psi_{s,p} , whose columns span the projection of \textrm{column\_span}(\Phi_{s,p}) onto the (D-d) -dimensional subspace given by \left(\textrm{column\lx@text@underline{ }span}(\Phi_{s-1,p^{\prime}})\right)^{\perp}\subset\mathbb{R}^{D} . The approximation to \vec{x}\in X\cap C_{s,p} at scale s is \vec{x}_{s}:=\Phi_{s,p}\Phi^{T}_{s,p}(\vec{x}-\vec{c}_{s,p})+\vec{c}_{s,p}. The wavelet bases and constants allow data points in X to be compactly represented in terms of the telescoping sum \vec{x}=\vec{x}_{1}+\sum^{\infty}_{s=2}(\vec{x}_{s}-\vec{x}_{s-1}) , representing the differences between the approximations of \vec{x} on consecutive scales as rapidly decaying updates [ 6 ] . This construction satisfies the assumptions in [ 10 ] , giving probabilistic bounds on the performance of the GMRA approximation under mild assumptions on the underlying distribution of the data. 3 Updating Manifolds A benefit of the non-linear manifold constructed described in section 2 is the simplicity of the update procedure for an existing non-linear manifold given more data. In particular, the covertree structure allows for the easy insertion of data [ 9 ] , and more importantly, preserves the existing partitioning of the dataset at each scale s unless the manifold changes drastically (requiring additional partitions), in which case the low-dimensional non-linear manifold is not sufficiently accurate, or an

Read the complete text