Space partitions of underlie a vast and important class of fast nearest neighbor search (NNS) algorithms. Inspired by recent theoretical work on NNS for general metric spaces [Andoni, Naor, Nikolov, Razenshteyn, Waingarten STOC 2018, FOCS 2018], we develop a new framework for building space partitions re…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “space partitioning”
A survey of mass partitionsmath.CO
Survey of mass partition problems in geometry and topology.
problem Inducing partitions on measures or sets by dividing space.
method Recent progress in topology, discrete geometry, and computer science.
result Connections between different fields.
Optimizes Lipschitz estimates for partitions of unity and characterizes spaces with Assouad-Nagata dimension.
problem Understanding the properties of partitions of unity and their Lipschitz bounds.
method Analyzes the standard partition of unity and its -generalizations, using the approximate midpoint property and Lebesgue number.
result Optimal Lipschitz bounds for partitions of unity and characterizes metric spaces with Assouad-Nagata dimension.
Although consistency is a minimum requirement of any estimator, little is known about consistency of the mean partition approach in consensus clustering. This contribution studies the asymptotic behavior of mean partitions. We show that under normal assumptions, the mean partition approach is consistent and asymptotic …
The Binary Space Partitioning-Tree~(BSP-Tree) process was recently proposed as an efficient strategy for space partitioning tasks. Because it uses more than one dimension to partition the space, the BSP-Tree Process is more efficient and flexible than conventional axis-aligned cutting strategies. However, due to its ba…
Fitting statistical models is computationally challenging when the sample size or the dimension of the dataset is huge. An attractive approach for down-scaling the problem size is to first partition the dataset into subsets and then fit using distributed algorithms. The dataset can be partitioned either horizontally (i…
Standard bubbles and partitions are stable in various model spaces.
problem Stability of standard bubbles and partitions in different model spaces.
method New conjugated Brascamp-Lieb inequality and conformally flattening boundary potential.
result Stability of standard bubbles and partitions in , , and .
Rectangular Bounding Processstat.ML
Stochastic partition models divide a multi-dimensional space into a number of rectangular regions, such that the data within each region exhibit certain types of homogeneity. Due to the nature of their partition strategy, existing partition models may create many unnecessary divisions in sparse regions when trying to d…
Unsupervised space partitioning improves ANNS performance without pre-processing.
problem Efficient nearest neighbor search in high-dimensional spaces.
method Custom unsupervised learning framework for space partitioning and learning-to-search.
result Our method outperforms state-of-the-art approaches on ANNS benchmarks.
Locally isoperimetric partitions minimize perimeter in space.
problem Finding minimal perimeter partitions in space.
method Proving closure theorem to limit sequences of isoperimetric clusters.
result Examples of isoperimetric partitions in various dimensions.
New proof of a unique 3-part partition in 8D space.
problem Existence of a non-standard isoperimetric partition in high dimensions.
method Analytical proof showing existence of a specific partition.
result Existence of a non-standard isoperimetric partition in 8D space.
Bayesian nonparametric method partitions shapes using curves.
problem Capturing complex shapes in multi-dimensional data.
method Proposes a novel spline partitioning approach using curves.
result Demonstrates improved shape modeling compared to existing methods.
State space partitioning based on constrained spectral clustering for block particle filteringstat.ML
A new method for state space partitioning in block particle filtering reduces bias and variance.
problem Overcoming the curse of dimensionality in non-linear, non-Gaussian state space estimation.
method Formulates state space partitioning as a clustering problem and uses spectral clustering with constraints.
result The proposed method effectively groups correlated state variables into smaller blocks, reducing bias and variance.
POUnets combine partitions of unity and monomials for efficient deep learning.
problem Efficiently approximating functions with deep neural networks in high dimensions.
method Integrates partitions of unity and monomials into neural network architecture.
result POUnets achieve hp-convergence for smooth functions and outperform MLPs for discontinuous functions.
LA-MCTS learns search space partition for black-box optimization using Monte Carlo Tree Search.
problem High-dimensional black-box optimization challenges.
method LA-MCTS recursively splits search space into regions with high/low function values, learns nonlinear partition and local models online.
result LA-MCTS achieves strong performance in black-box optimization and reinforcement learning benchmarks, especially for high-dimensional problems.
The Mondrian process represents an elegant and powerful approach for space partition modelling. However, as it restricts the partitions to be axis-aligned, its modelling flexibility is limited. In this work, we propose a self-consistent Binary Space Partitioning (BSP)-Tree process to generalize the Mondrian process. Th…
The study explores continuous noncrossing partitions and their relation to weighted circular factorizations.
problem Understanding the structure of continuous noncrossing partitions on the unit circle.
method Analyzes degree-d continuous noncrossing partitions and their equivalence classes of weighted linear factorizations.
result Maximal elements in the poset of continuous noncrossing partitions form a subspace homeomorphic to the dual Garside classifying space for the d-strand braid group.
Random Tessellation Forestsstat.ML
Space partitioning methods such as random forests and the Mondrian process are powerful machine learning methods for multi-dimensional and relational data, and are based on recursively cutting a domain. The flexibility of these methods is often limited by the requirement that the cuts be axis aligned. The Ostomachion p…
Minimal partitions with minimal perimeter found in metric spaces.
problem Finding minimal partitions with minimal perimeter in metric spaces.
method Existence proof and regularity analysis of minimal domains.
result Existence and regularity of minimal partitions in various metric spaces.
A dependent partition-valued process for multitask clustering and time evolving network modellingstat.ML
The fundamental aim of clustering algorithms is to partition data points. We consider tasks where the discovered partition is allowed to vary with some covariate such as space or time. One approach would be to use fragmentation-coagulation processes, but these, being Markov processes, are restricted to linear or tree s…
Paper proposes a new method to learn EBMs and their partition function.
problem Intractability of exact MLE for EBMs due to partition function computation.
method Jointly learns an energy model and its log-partition function using neural networks.
result First tractable method for optimizing sparsemax loss in large spaces.
Researchers approximate partition functions on Riemannian spaces in the large N limit.
problem Computing normalization factors (partition functions) on Riemannian symmetric spaces is challenging.
method Approximation techniques in the large N limit, including saddle-point equations.
result Formulas for leading order terms in the large N limit of SPD matrices and related spaces.
Partition Tree estimates conditional densities for mixed continuous and categorical variables.
problem Estimating conditional densities for mixed data types.
method Tree-based framework modeling conditional distributions as piecewise-constant densities on adaptive partitions, minimizing conditional negative log-likelihood.
result Improved probabilistic prediction compared to CART-style trees and state-of-the-art methods.
Bayesian nonparametric space partition (BNSP) models provide a variety of strategies for partitioning a -dimensional space into a set of blocks. In this way, the data points lie in the same block would share certain kinds of homogeneity. BNSP models can be applied to various areas, such as regression/classification …
New model of vague knowledge without strict partitions or transitivity.
problem Standard economic models of information fail to capture real-world vague knowledge.
method Relaxing assumptions of transitivity and partition structure to formalize vague knowledge.
result Vague knowledge can distinguish some states but not partition the state space.
Definition of the partition function of U(1) gauge theory is extended to a class of four-manifolds containing all compact spaces and certain asymptotically locally flat (ALF) ones including the multi-Taub--NUT spaces. The partition function is calculated via zeta-function regularization with special attention to its mo…
Novel method recursively partitions sample space for density estimation.
problem Estimating complex density functions efficiently and accurately.
method Recursive partitioning of the sample space, asymptotically exact.
result Asymptotically exact approximation of any density function.
This paper tackles multi-modal label disentanglement in partition-based XMC.
problem Existing partition-based XMC methods create mutually exclusive clusters, which is sub-optimal for multi-modal labels.
method Formulates label assignment as an optimization problem to maximize precision rates, creating flexible and overlapped label clusters.
result Successfully disentangles multi-modal labels, leading to state-of-the-art results on XMC benchmarks.
Develops an MS-inspired algorithm for regression mode finding and space partitioning.
problem Finding local modes of regression functions and partitioning input space.
method Mean-shift-inspired algorithm for iterative gradient ascent.
result Proves convergence and rates of convergence for estimated local modes.
Improved supervised EM learning for shared kernel models with feature space partitioning.
problem Lack of rigour in EM derivation and high computational complexity.
method Detailed derivation of EM for Gaussian shared kernel model, feature space partitioning to reduce complexity.
result Improved performance at reduced complexity achieved.
There are two natural simplicial complexes associated to the noncrossing partition lattice: the order complex of the full lattice and the order complex of the lattice with its bounding elements removed. The latter is a complex that we call the noncrossing partition link because it is the link of an edge in the former. …
New findings on maximizing noise stability in partitions of Gaussian space.
problem Maximizing noise stability in partitions of Gaussian space.
method Analyzing the correlation between sets and their noise stability, proving conditional conjectures and hardness results.
result Hyperstable partitions maximize noise stability and have specific properties.
ParK efficiently solves kernel ridge regression for large datasets.
problem Large-scale kernel ridge regression efficiency and accuracy.
method Partitioning feature space with random projections and iterative optimization.
result Provably maintains statistical accuracy with reduced space and time complexity.
Multi-view clustering is an important yet challenging task due to the difficulty of integrating the information from multiple representations. Most existing multi-view clustering methods explore the heterogeneous information in the space where the data points lie. Such common practice may cause significant information …
An Equal-Probability Partition of the Sample Space: A Non-parametric Inference from Finite Samplesstat.ML
This paper finds a unique partition of a sample space for estimating continuous distributions.
problem Estimating continuous probability distributions from finite samples.
method Equal-probability partition of the sample space using order statistics.
result The partition yields an entropy of log2(N+1) bits, providing a discrete entropy estimate.
This paper presents Sparse Partitioning, a Bayesian method for identifying predictors that either individually or in combination with others affect a response variable. The method is designed for regression problems involving binary or tertiary predictors and allows the number of predictors to exceed the size of the sa…
We study 4-dimensional higher-derivative conformal higher spin (CHS) fields generalising Weyl graviton and conformal gravitino. They appear, in particular, as "induced" theories in the AdS/CFT context. We consider their partition function on curved Einstein-space backgrounds like (A)dS or sphere and Ricci-flat spaces. …
The method learns to partition event time space for better prediction.
problem Improving event time prediction in clinical settings with limited data.
method Develops a method to learn cut points for partitioning event time space.
result Improved prediction performance on real-world datasets.
We explore the geometrical interpretation of the PCA based clustering algorithm Principal Direction Divisive Partitioning (PDDP). We give several examples where this algorithm breaks down, and suggest a new method, gap partitioning, which takes into account natural gaps in the data between clusters. Geometric features …
A new method detects concept drift in streaming data using k-means space partitioning.
problem Detecting distribution changes in streaming data.
method Equal intensity k-means space partitioning (EI-kMeans) and heuristic sensitivity improvement.
result EI-kMeans improves drift detection accuracy and sensitivity.
A post-hoc framework improves model performance by calibrating different feature spaces.
problem Improving AUC performance on binary classification tasks for overconfident models.
method Identifies heterogeneous partitions of the feature space and applies post-hoc calibration techniques to each partition.
result Theoretical optimality of the framework for any model, demonstrated on deep neural networks.
We introduce a novel approach to feed-forward neural network interpretation based on partitioning the space of sequences of neuron activations. In line with this approach, we propose a model-specific interpretation method, called YASENN. Our method inherits many advantages of model-agnostic distillation, such as an abi…
A high-order recombination algorithm for weak approximation of stochastic differential equationsmath.PR
Paper develops a high-order recombination algorithm for financial modeling.
problem Creating accurate approximations of stochastic differential equations in finance.
method High-order recombination method applied to practical financial problems.
result Algorithm effectively avoids explosive growth in support cardinality for high-order approximations.
Algorithm learns diffusion processes with high-dimensional state spaces.
problem Stochastic control of unbounded diffusion processes with high-dimensional state spaces.
method Adaptive partitioning and learning algorithm that refines discretization based on estimation bias and statistical confidence.
result Established regret bounds that depend on problem parameters, extending to unbounded diffusion processes.
In this article, the logic rule ensembles approach to supervised learning is applied to the unsupervised or semi-supervised clustering. Logic rules which were obtained by combining simple conjunctive rules are used to partition the input space and an ensemble of these rules is used to define a similarity matrix. Simila…
Study optimal partitions on spheres using fractional Q-curvature and variational methods.
problem Optimal partition problem on the sphere with fractional Q-curvature.
method Variational approach, symmetry analysis, Hölder regularity results.
result Existence of a symmetric minimal partition.
Chern-Simons theory on a closed contact three-manifold is studied when the Lie group for gauge transformations is compact, connected and abelian. A rigorous definition of an abelian Chern-Simons partition function is derived using the Faddeev-Popov gauge fixing method. A symplectic abelian Chern-Simons partition functi…
New method connects neural networks to diagrammatic algebra.
problem Constructing permutation equivariant neural networks.
method Schur-Weyl duality between symmetric group and partition algebra.
result Simple diagrammatic method for calculating weight matrices.