Finding discrete local maximizers

Discrete local maximizers

Let $r\in \mathbb R^d$ be fixed and such that all of its components are positive. Define $B(x,r):=\{y\in \mathbb R^d: |x_j-y_j|\leq r_j, \forall j=1,...,d\}$ the ball centered at $x\in \mathbb R^d$ with radius $r$. A discrete function is any map $f: X \longrightarrow \mathbb R$, where $X$ is a discrete set of $n$ points in $\mathbb R^d$.
An $x\in X$ is said to be a discrete local maximizer of $f$ if $f(y)\geq f(x)$ for all $y\in B(x, r)$.

In this post I propose a combinatorial algorithm with complexity $O(n^2)$ ($n$ is the input size, $d$ is fixed) finding all discrete local maximizers of a given discrete function $f$.
The idea is simple, we first pre-compute the distances between any two points and then check one by one if it is a discrete local maximizer or not.

import torch
import matplotlib.pyplot as plt
torch.manual_seed(123)  

def  pseudo_local_maxers(points, values, radii="auto", max_nb="auto"):
	"""Find all discrete local maximizers
	points: X
	values: f(X)
	radii: r
	max_nb: max number of discrete local maximizers
	"""
	if radii=="auto":
		radii=1e-2
	if max_nb=="auto":
		max_nb=points.size(1)
	d, n = points.shape
	dist_matrix = (points.T.view(n, d, 1)-points).abs()
	close = (dist_matrix <= radii).all(1) 
	
	ids = []
	for i in  range(max_nb):
		v = values[i]
		if v >= values[close[:, i]].max():
		ids += [i] 

	out = {
		"maximizers": points[:, ids],
		"maxima": values[ids],
		"indices": ids,
	}
	return out

def  example():
	d, n = 2, 50
	points = torch.rand(d, n)
	values = torch.rand(n)
	eps=2e-1
	radii=torch.tensor([[eps], [eps]])

	out = pseudo_local_maxers(points, values, radii=radii, max_nb="auto")
	maxers = out["maximizers"]
	maxima = out["maxima"]
	plt.scatter(points[0], points[1], c=values, s=200, label="points" )
	plt.scatter(maxers[0], maxers[1], c="k", s=50, marker="^", label="maxers")
	plt.colorbar()
	plt.legend()
	print(f"nb of discrete local maxima {len(maxima)}")

example()

The result is