We introduce and study the notion of *an outer biLipschitz extension* of a map between Euclidean spaces. The notion is a natural analogue of the notion of *a Lipschitz extension* of a Lipschitz map. We show that for every map f there exists an outer biLipschitz extension f′ whose distortion is greater than that of f by at most a constant factor. This result can be seen as a counterpart of the classic Kirszbraun theorem for outer biLipschitz extensions. We also study outer biLipschitz extensions of nearisometric maps and show upper and lower bounds for them. Then, we present applications of our results to prioritized and terminal dimension reduction problems, described next. We prove a *prioritized* variant of the Johnson–Lindenstrauss lemma: given a set of points X⊂ ℝd of size N and a permutation (”priority ranking”) of X, there exists an embedding f of X into ℝO(logN) with distortion O(loglogN) such that the point of rank j has only O(log3 + ε j) nonzero coordinates – more specifically, all but the first O(log3+ε j) coordinates are equal to 0; the distortion of f restricted to the first j points (according to the ranking) is at most O(loglogj). The result makesmore »
TwoSided Kirszbraun Theorem
In this paper, we prove a twosided variant of the Kirszbraun theorem. Consider an arbitrary subset X of Euclidean space and its superset Y. Let f be a 1Lipschitz map from X to ℝ^m. The Kirszbraun theorem states that the map f can be extended to a 1Lipschitz map ̃ f from Y to ℝ^m. While the extension ̃ f does not increase distances between points, there is no guarantee that it does not decrease distances significantly. In fact, ̃ f may even map distinct points to the same point (that is, it can infinitely decrease some distances). However, we prove that there exists a (1 + ε)Lipschitz outer extension f̃:Y → ℝ^{m'} that does not decrease distances more than "necessary". Namely, ‖f̃(x)  f̃(y)‖ ≥ c √{ε} min(‖xy‖, inf_{a,b ∈ X} (‖x  a‖ + ‖f(a)  f(b)‖ + ‖by‖)) for some absolutely constant c > 0. This bound is asymptotically optimal, since no LLipschitz extension g can have ‖g(x)  g(y)‖ > L min(‖xy‖, inf_{a,b ∈ X} (‖x  a‖ + ‖f(a)  f(b)‖ + ‖by‖)) even for a single pair of points x and y.
In some applications, one is interested in the distances ‖f̃(x)  f̃(y)‖ between more »
 Editors:
 Buchin, Kevin; Colin de Verdiere, Eric
 Publication Date:
 NSFPAR ID:
 10281595
 Journal Name:
 Leibniz international proceedings in informatics
 Volume:
 189
 Page Range or eLocationID:
 13:113:14
 ISSN:
 18688969
 Sponsoring Org:
 National Science Foundation
More Like this


A gr e at d e al of i nt er e st s urr o u n d s t h e u s e of tr a n s cr a ni al dir e ct c urr e nt sti m ul ati o n (t D C S) t o a u g m e nt c o g niti v e tr ai ni n g. H o w e v er, eff e ct s ar e i n c o n si st e nt a cr o s s st u di e s, a n d m et aa n al yti c e vi d e n c e i s mi x e d, e s p e ci all y f o r h e alt h y, y o u n g a d ult s. O n e m aj or s o ur c e of t hi s i n c o n si st e n c y i s i n di vi d u al diff er e n c e s a m o n g t h e pmore »

Abstract Recently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs (J Graph Theory 92(3):191–206, 2019, https://doi.org/10.1002/jgt.22447 ). In this new setting, each vertex v in some subset of V ( G ) has a request for a certain color r ( v ) in its list of colors L ( v ). The goal is to find an L coloring satisfying many, but not necessarily all, of the requests. The main studied question is whether there exists a universal constant $$\varepsilon >0$$ ε > 0 such that any graph G in some graph class $$\mathscr {C}$$ C satisfies at least $$\varepsilon$$ ε proportion of the requests. More formally, for $$k > 0$$ k > 0 the goal is to prove that for any graph $$G \in \mathscr {C}$$ G ∈ C on vertex set V , with any list assignment L of size k for each vertex, and for every $$R \subseteq V$$ R ⊆ V and a request vector $$(r(v): v\in R, ~r(v) \in L(v))$$ ( r ( v ) : v ∈ R , r ( v ) ∈ L ( v ) ) , there exists an L coloring of Gmore »

Obeid, Iyad Selesnick (Ed.)Electroencephalography (EEG) is a popular clinical monitoring tool used for diagnosing brainrelated disorders such as epilepsy [1]. As monitoring EEGs in a criticalcare setting is an expensive and tedious task, there is a great interest in developing realtime EEG monitoring tools to improve patient care quality and efficiency [2]. However, clinicians require automatic seizure detection tools that provide decisions with at least 75% sensitivity and less than 1 false alarm (FA) per 24 hours [3]. Some commercial tools recently claim to reach such performance levels, including the Olympic Brainz Monitor [4] and Persyst 14 [5]. In this abstract, we describe our efforts to transform a highperformance offline seizure detection system [3] into a low latency realtime or online seizure detection system. An overview of the system is shown in Figure 1. The main difference between an online versus offline system is that an online system should always be causal and has minimum latency which is often defined by domain experts. The offline system, shown in Figure 2, uses two phases of deep learning models with postprocessing [3]. The channelbased long short term memory (LSTM) model (Phase 1 or P1) processes linear frequency cepstral coefficients (LFCC) [6] features from each EEGmore »

F or c e d at a f or a fl a p pi n g f oil e n er g y h ar v e st er wit h a cti v e l e a di n g e d g e m oti o n o p er ati n g i n t h e l o w r e d u c e d fr e q u e n c y r a n g e i s c oll e ct e d t o d et er mi n e h o w l e a di n g e d g e m oti o n aff e ct s e n er g y h ar v e sti n g p erf or m a n c e. T h e f oil pi v ot s a b o ut t h e mi dc h or d a n d o p er at e s i n t h e l o w r e d u c e d fr e q u e n c y r a n g e of 𝑓𝑓more »