BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

David Levin

David Levin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.NANumerical AnalysisGraphicsMachine LearningComputational GeometryComputer VisionDiscrete Mathematicsmath.COmath.DGmath.PR

Catalog footprint

What is connected

9works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2022arXiv

Global and explicit approximation of piecewise smooth 2D functions from cell-average data

Given cell-average data values of a piecewise smooth bivariate function $f$ within a domain $Ω$, we look for a piecewise adaptive approximation to $f$. We are interested in an explicit and global (smooth) approach. Bivariate approximation techniques, as trigonometric or splines approximations, achieve reduced approximation orders near the boundary of the domain and near curves of jump singularities of the function or its derivatives. Whereas the boundary of $Ω$ is assumed to be known, the subdivision of $Ω$ to subdomains on which $f$ is smooth is unknown. The first challenge of the proposed approximation algorithm would be to find a good approximation to the curves separating the smooth subdomains of $f$. In the second stage, we simultaneously look for approximations to the different smooth segments of $f$, where on each segment we approximate the function by a linear combination of basis functions $\{p_i\}_{i=1}^M$, considering the corresponding cell-averages. A discrete Laplacian operator applied to the given cell-average data intensifies the structure of the singularity of the data across the curves separating the smooth subdomains of $f$. We refer to these derived values as the signature of the data, and we use it for both approximating the singularity curves separating the different smooth regions of $f$. The main contributions here are improved convergence rates to both the approximation of the singularity curves and the approximation of $f$, an explicit and global formula, and, in particular, the derivation of a piecewise smooth high order approximation to the function.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Manifold Repairing, Reconstruction and Denoising from Scattered Data in High-Dimension

We consider a problem of great practical interest: the repairing and recovery of a low-dimensional manifold embedded in high-dimensional space from noisy scattered data. Suppose that we observe a point cloud sampled from the low-dimensional manifold, with noise, and let us assume that there are holes in the data. Can we recover missing information inside the holes? While in low-dimension the problem was extensively studied, manifold repairing in high dimension is still an open problem. We introduce a new approach, called Repairing Manifold Locally Optimal Projection (R-MLOP), that expands the MLOP method introduced by Faigenbaum-Golovin et al. in 2020, to cope with manifold repairing in low and high-dimensional cases. The proposed method can deal with multiple holes in a manifold. We prove the validity of the proposed method, and demonstrate the effectiveness of our approach by considering different manifold topologies, for single and multiple holes repairing, in low and high dimensions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Approximation of Functions over Manifolds: A Moving Least-Squares Approach

We present an algorithm for approximating a function defined over a $d$-dimensional manifold utilizing only noisy function values at locations sampled from the manifold with noise. To produce the approximation we do not require any knowledge regarding the manifold other than its dimension $d$. We use the Manifold Moving Least-Squares approach of (Sober and Levin 2016) to reconstruct the atlas of charts and the approximation is built on-top of those charts. The resulting approximant is shown to be a function defined over a neighborhood of a manifold, approximating the originally sampled manifold. In other words, given a new point, located near the manifold, the approximation can be evaluated directly on that point. We prove that our construction yields a smooth function, and in case of noiseless samples the approximation order is $\mathcal{O}(h^{m+1})$, where $h$ is a local density of sample parameter (i.e., the fill distance) and $m$ is the degree of a local polynomial approximation, used in our algorithm. In addition, the proposed algorithm has linear time complexity with respect to the ambient-space's dimension. Thus, we are able to avoid the computational complexity, commonly encountered in high dimensional approximations, without having to perform non-linear dimension reduction, which inevitably introduces distortions to the geometry of the data. Additionaly, we show numerical experiments that the proposed approach compares favorably to statistical approaches for regression over manifolds and show its potential.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Manifold Approximation by Moving Least-Squares Projection (MMLS)

In order to avoid the curse of dimensionality, frequently encountered in Big Data analysis, there was a vast development in the field of linear and nonlinear dimension reduction techniques in recent years. These techniques (sometimes referred to as manifold learning) assume that the scattered input data is lying on a lower dimensional manifold, thus the high dimensionality problem can be overcome by learning the lower dimensionality behavior. However, in real life applications, data is often very noisy. In this work, we propose a method to approximate $\mathcal{M}$ a $d$-dimensional $C^{m+1}$ smooth submanifold of $\mathbb{R}^n$ ($d \ll n$) based upon noisy scattered data points (i.e., a data cloud). We assume that the data points are located "near" the lower dimensional manifold and suggest a non-linear moving least-squares projection on an approximating $d$-dimensional manifold. Under some mild assumptions, the resulting approximant is shown to be infinitely smooth and of high approximation order (i.e., $O(h^{m+1})$, where $h$ is the fill distance and $m$ is the degree of the local polynomial approximation). The method presented here assumes no analytic knowledge of the approximated manifold and the approximation algorithm is linear in the large dimension $n$. Furthermore, the approximating manifold can serve as a framework to perform operations directly on the high dimensional data in a computationally efficient manner. This way, the preparatory step of dimension reduction, which induces distortions to the data, can be avoided altogether.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Reconstruction of piecewise-smooth multivariate functions from Fourier data

In some applications, one is interested in reconstructing a function $f$ from its Fourier series coefficients. The problem is that the Fourier series is slowly convergent if the function is non-periodic, or is non-smooth. In this paper, we suggest a method for deriving high order approximation to $f$ using a Padé-like method. Namely, by fitting some Fourier coefficients of the approximant to the given Fourier coefficients of $f$. Given the Fourier series coefficients of a function on a rectangular domain in $\mathbb{R}^d$, assuming the function is piecewise smooth, we approximate the function by piecewise high order spline functions. First, the singularity structure of the function is identified. For example in the 2-D case, we find high accuracy approximation to the curves separating between smooth segments of $f$. Secondly, simultaneously we find the approximations of all the different segments of $f$. We start by developing and demonstrating a high accuracy algorithm for the 1-D case, and we use this algorithm to step up to the multidimensional case.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Computer Aided Restoration of Handwritten Character Strokes

This work suggests a new variational approach to the task of computer aided restoration of incomplete characters, residing in a highly noisy document. We model character strokes as the movement of a pen with a varying radius. Following this model, a cubic spline representation is being utilized to perform gradient descent steps, while maintaining interpolation at some initial (manually sampled) points. The proposed algorithm was utilized in the process of restoring approximately 1000 ancient Hebrew characters (dating to ca. 8th-7th century BCE), some of which are presented herein and show that the algorithm yields plausible results when applied on deteriorated documents.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

High order approximation to non-smooth multivariate functions

Approximations of non-smooth multivariate functions return low-order approximations in the vicinities of the singularities. Most prior works solve this problem for univariate functions. In this work we introduce a method for approximating non-smooth multivariate functions of the form $f = g + r_+$ where $g,r \in C^{M+1}(\mathbb{R}^n)$ and the function $r_+$ is defined by \[ r_+(y) = \left\{ \begin{array}{ll} r(y), & r(y) \geq 0 \\ 0, & r(y) < 0 \end{array} \right. \ , \ \forall y \in \mathbb{R}^n \ . \] Given scattered (or uniform) data points $X \subset \mathbb{R}^n$, we investigate approximation by quasi-interpolation. We design a correction term, such that the corrected approximation achieves full approximation order on the entire domain. We also show that the correction term is the solution to a Moving Least Squares (MLS) problem, and as such can both be easily computed and is smooth. Last, we prove that the suggested method includes a high-order approximation to the locations of the singularities.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings

We give the first polynomial upper bound on the mixing time of the edge-flip Markov chain for unbiased dyadic tilings, resolving an open problem originally posed by Janson, Randall, and Spencer in 2002. A dyadic tiling of size n is a tiling of the unit square by n non-overlapping dyadic rectangles, each of area 1/n, where a dyadic rectangle is any rectangle that can be written in the form [a2^{-s}, (a+1)2^{-s}] \times [b2^{-t}, (b+1)2^{-t}] for non-negative integers a,b,s,t. The edge-flip Markov chain selects a random edge of the tiling and replaces it with its perpendicular bisector if doing so yields a valid dyadic tiling. Specifically, we show that the relaxation time of the edge-flip Markov chain for dyadic tilings is at most O(n^{4.09}), which implies that the mixing time is at most O(n^{5.09}). We complement this by showing that the relaxation time is at least Ω(n^{1.38}), improving upon the previously best lower bound of Ω(n\log n) coming from the diameter of the chain.

0 citations0 reviewsNo code linkedOpen access