Metadata-Version: 2.4
Name: lipfit
Version: 0.1.1
Summary: LipFit
Author: Gleb Beliakov
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE.txt
Requires-Dist: torch>=2.0
Dynamic: license-file

![Python](https://img.shields.io/badge/python-3.9+-blue.svg)
![PyTorch](https://img.shields.io/badge/PyTorch-GPU-orange.svg)
# 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](https://arxiv.org/abs/2606.04670)

## Installation
To install type:
```python
$ pip install lipfit
```

---

## Quick Example

```python
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 

```python
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 
```python
dim = 3
reservedata=100000
LL =  LipFit(reservedata,dim, 1, device)
```

### Example how to add data
```python
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


```python
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
```python
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
```python
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
```python
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:
```python
$ tests/test.py
```
