lipfit 0.1.1

LipFit

lipfit

LipFit is a GPU-accelerated library for multivariate scattered-data interpolation and fitting based on Lipschitz-optimal interpolation principles.

The method can be viewed as a continuous alternative to k-nearest-neighbour (kNN) approximation and natural-neighbour interpolation. In contrast to standard kNN methods, the neighbours influencing a query point are selected from all directions around the point, rather than simply by distance ordering. This produces continuous and Lipschitz-continuous approximations (which is a stronger property) instead of piecewise-discontinuous predictions.

For a query point q, LipFit computes:

• the smallest value a Lipschitz function consistent with the data can attain at distance d,
• and the largest value such a function can attain.

These bounds define an interval containing every admissible Lipschitz interpolation of the data. The optimal prediction — in the minimax (best worst-case) sense — is taken as the midpoint of this interval.

When k=1, the method performs exact Lipschitz interpolation using one neighbour for the upper bound and one other for the lower bound.

For k>1, LipFit computes weighted averages of multiple local bounds, producing smooth approximations suitable for noisy data. In this mode, the method behaves similarly to a smoothing kNN scheme while preserving continuity and Lipschitz regularity.

---

Main Features

• GPU-accelerated evaluation and fitting using PyTorch
• Lipschitz-continuous interpolation
• No training required, just data
• Exact interpolation or smooth approximation
• Support for high-dimensional scattered data
• Local and global Lipschitz models
• Automatic estimation of Lipschitz constants from data
• Monotonicity constraints in individual variables
• Region-wise monotonicity constraints
• Incremental addition of new data without retraining
• Numerically stable construction and evaluation
• Smoothing the data

---

Lipschitz Properties

The Lipschitz interpolant possesses several desirable theoretical and numerical properties:

• preservation of data ranges,
• continuous dependence on the data,
• preservation of Lipschitz regularity,
• strong approximation guarantees,
• stable evaluation without accumulation of errors,
• explicit error bounds,
• no iterative training process.

If the data are noisy, LipFit can construct smooth approximations that satisfy prescribed Lipschitz and monotonicity constraints.

The library also supports locally Lipschitz approximations, allowing the model to adapt to regions with different smoothness properties while avoiding excessive oscillations.

The global Lipschitz constant may either be supplied by the user or estimated automatically from the dataset.

---

Documentation

Methods and examples

Installation

To install type:

$ pip install lipfit

---

Quick Example

import torch
from lipfit import LipFit

device = "cuda"

dim = 3
LF = LipFit(
    reservedata=100000,
    dim=dim,
    k=1,
    device=device
)

X = torch.rand(1500, dim)
Y = torch.sin(X[:,0])

LF.add(X, Y)

Q = torch.rand(100, dim)

Yq = LF.values(Q, LC=2.0, model=0, k=1)

Usage of the library

from lipfit import LipFit

Follow these steps in your Python code to use the library:

• Initialize on the device
• add data
• calculate values at query points
• optional: use monotonicity conditions if known/desired
• optional: calculate/estimate Lipschitz constant LC
• optional: calculate local Lipschitz constants and use local_values
• optional: smoothen the data
• optional: add new data

---

Example how to initialize

dim = 3
reservedata=100000
LL =  LipFit(reservedata,dim, 1, device)

Example how to add data

ndata = 1500
x = torch.rand(ndata, dim)
y = torch.zeros(ndata)

for i in range(0,M):
    y[i]=torch.sin(x[i,0])+0.5*torch.sin(5*x[i,1]) + x[i,2]
    
LL.clear()    #only if removing previous data
LL.add(x,y)

Example how to fit values

from lipfit import LipFit

dim = 3
reservedata=100000
LL =  LipFit(reservedata,dim, 1, device)
LL.add(x,y)
ntest=100 #test data
q = torch.rand(ntest, dim)
yp=LL.values(q, 2.0, 0, 1) # guess Lip constant 2
LL.add(newx,newy)
yp=LL.values(q, 0.5, 0, 1) # guess Lip constant 0.5
# can use LL.smooth_lipschitz(0.5,0) before values to smoothen the data

Example how to use monotonicity

from lipfit import LipFit

dim = 3
reservedata=100000
LL =  LipFit(reservedata,dim, 1, device)
LL.add(x,y)
mon=[1,-1,0]
a=[0,0,-1] #optional for regions
b=[1,1,2]
w=[1,0,0,0,0] #optional for k>1
LL.setparams(mon,a,b,w)
LC=LL.lipschitz_constant() # actually calculate LC 
ntest=100 #test data
q = torch.rand(ntest, dim)
yp=LL.values(q, LC, 1, 1) # model=1 (monotonicity)

Example how to use Local Lipschitz

from lipfit import LipFit

dim = 3
reservedata=100000
LL =  LipFit(reservedata,dim, 1, device)
LL.add(x,y)
LL.compute_local_lipschitz(S=8)

ntest=100 #test data
q = torch.rand(ntest, dim)
yp=LL.values(q, 2.0, 0, 1) # guess Lip constant 2

Example how to use Lipschitz smoothing

from lipfit import LipFit

dim = 3
reservedata=100000
LL =  LipFit(reservedata,dim, 1, device)
LL.add(x,y)
LL.smooth_lipschitz(0.5,0)

ntest=100 #test data
q = torch.rand(ntest, dim)
yp=LL.values(q, 0.5, 0, 1) # guess Lip constant 0.5
#can also be done with monotonicity model=1 and after setting mon

---

LipFit

Main fitting class.

Parameters

Parameter	Type	Description
reservedata	int	Initial storage capacity for samples
dim	int	Input dimension
k neighbours	int	Number of closest neighbours to use (one for interpolation)
device	str or torch.device	Computation device ("cpu" or "cuda" or "mps")

---

Methods

add(X, Y)

Adds samples to the internal dataset (to device).

Parameters

Parameter	Type	Shape	Description
X	torch.Tensor	(M, dim)	Input samples
Y	torch.Tensor	(M,)	Target values

Notes

• Capacity is expanded automatically if needed.
• Data may reside on CPU or GPU.

---

clear()

Removes samples from the internal dataset (on device). Does not reallocate memory, just sets dataset size to 0.

---

values(q, LC, model,k)

Evaluates fitting model at query points

Parameters

Parameter	Type	Shape	Description
Q	torch.Tensor or np.array	(K, dim)	Query points
LC	float	a guesstimate of Lipschitz constant
model	int	0 for normal, 1 for monotone, 2 for monotone in regions
k	int	Number of closest neighbours to use (one for interpolation)

Returns

Type	Shape	Description
torch.Tensor	(K)	Predicted values

---

setparams(mon, a, b, w)

Sets monotonicity constraints, monotonic regions, and weights used in nearest-neighbour calculations.

Parameters

Parameter	Type	Description
mon	torch.Tensor or array-like (dim)	Monotonicity types for each dimension
a	torch.Tensor or array-like (dim)	Lower bounds of monotonic regions
b	torch.Tensor or array-like (dim)	Upper bounds of monotonic regions
w	torch.Tensor or array-like (k)	Weights used in knn calculations

Notes

• Required for monotonic models.
• Weights are used in KNN-style local computations and add to 1.

---

lipschitz_constant(block_size=1024, eps=1e-10)

Computes the global Lipschitz constant of the dataset using all pairwise distances.

Parameters

Parameter	Type	Default	Description
block_size	int	1024	Block size used for pairwise computation
eps	float	1e-10	Small regularization value preventing division by zero

Returns

Type	Description
float	Scalar Lipschitz constant

Notes

• Computational complexity is approximately O(Ndata²).
• Uses batched computation to reduce memory usage.

---

lipschitz_anchor_sampling(num_anchors=512, samples_per_anchor=512, eps=1e-12)

Approximates the global Lipschitz constant using randomly sampled anchor points.

Parameters

Parameter	Type	Default	Description
num_anchors	int	512	Number of anchor points
samples_per_anchor	int	512	Number of neighbours sampled per anchor
eps	float	1e-12	Small regularization value preventing division by zero

Returns

Type	Description
float	Approximate Lipschitz constant

Notes

• Faster than full quadratic computation.
• Suitable for large datasets.

---

compute_local_lipschitz(S=16)

Computes local Lipschitz constants for all samples and approximates them using spline models.

Parameters

Parameter	Type	Default	Description
S	int	16	Number of spline knots used for approximation

Notes

• Must be recomputed whenever new data is added.
• Used by local Lipschitz prediction methods.
• Produces less rugged approximations with local Lipschitz behaviour.

---

values_local(Q, model, k)

Evaluates local Lipschitz predictions for query points.

Parameters

Parameter	Type	Description
Q	torch.Tensor or array-like	Query points, shape (M, dim)
model	int	Prediction model type (0, 1, or 2)
k	int	Number of nearest neighbours used (2k neighbours internally)

Returns

Type	Description
torch.Tensor	Predicted values at query points

Model Types

Value	Meaning
0	Standard local model
1	Monotone model
2	Region-wise monotone model

Notes

• Monotone models require calling setparams() beforehand.
• If k > 1, neighbour weights and parameters must be configured.
• Uses precomputed local Lipschitz approximations.
• Supports batched query evaluation.

---

smooth_lipschitz(LC, model)

Smoothens data using Lipschitz constant LC.

Parameters

Parameter	Type	Description
LC	float	Desired Lipschitz constant
model	int	model type (0 or 1 for monotonicity)

Returns

Type	Description
torch.Tensor	The norm of the corrections to y

Notes

• Should be recomputed whenever new data is added, but not necessarily.
• Can be used with model=1 after setting mon in setparams.
• Requires calculating and storing Ndata² distances, do not use for Ndata>50000
• Should be used on noisy data.
• The data y are modified to smoothened values.

---

Test

To unit test type:

$ tests/test.py