More Like this

1. Multipliers on bi-parameter Haar system Hardy spaces

   https://doi.org/10.1007/s00208-024-02887-9  

   Lechner, R.; Motakis, P.; Müller, P_F_X; Schlumprecht, Th (May 2024, Mathematische Annalen)

   Abstract Let$$(h_I)$$ $\left(h_I\right)$denote the standard Haar system on [0, 1], indexed by$$I\in \mathcal {D}$$ $I\in D$, the set of dyadic intervals and$$h_I\otimes h_J$$ $h_I\otimes h_J$denote the tensor product$$(s,t)\mapsto h_I(s) h_J(t)$$ $(s,t)\mapsto h_I\left(s\right)h_J\left(t\right)$,$$I,J\in \mathcal {D}$$ $I,J\in D$. We consider a class of two-parameter function spaces which are completions of the linear span$$\mathcal {V}(\delta ^2)$$ $V\left({\delta }^2\right)$of$$h_I\otimes h_J$$ $h_I\otimes h_J$,$$I,J\in \mathcal {D}$$ $I,J\in D$. This class contains all the spaces of the formX(Y), whereXandYare either the Lebesgue spaces$$L^p[0,1]$$ $L^p[0,1]$or the Hardy spaces$$H^p[0,1]$$ $H^p[0,1]$,$$1\le p < \infty $$ $1\le p<\infty$. We say that$$D:X(Y)\rightarrow X(Y)$$ $D:X\left(Y\right)\to X\left(Y\right)$is a Haar multiplier if$$D(h_I\otimes h_J) = d_{I,J} h_I\otimes h_J$$ $D(h_I\otimes h_J)=d_{I,J}{h}_I\otimes h_J$, where$$d_{I,J}\in \mathbb {R}$$ $d_{I,J}\in R$, and ask which more elementary operators factor throughD. A decisive role is played by theCapon projection$$\mathcal {C}:\mathcal {V}(\delta ^2)\rightarrow \mathcal {V}(\delta ^2)$$ $C:V\left({\delta }^2\right)\to V\left({\delta }^2\right)$given by$$\mathcal {C} h_I\otimes h_J = h_I\otimes h_J$$ $C{h}_I\otimes h_J=h_I\otimes h_J$if$$|I|\le |J|$$ $\left|I\right|\le \left|J\right|$, and$$\mathcal {C} h_I\otimes h_J = 0$$ $C{h}_I\otimes h_J=0$if$$|I| > |J|$$ $\left|I\right|>\left|J\right|$, as our main result highlights: Given any bounded Haar multiplier$$D:X(Y)\rightarrow X(Y)$$ $D:X\left(Y\right)\to X\left(Y\right)$, there exist$$\lambda ,\mu \in \mathbb {R}$$ $\lambda ,\mu \in R$such that$$\begin{aligned} \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C})\text { approximately 1-projectionally factors through }D, \end{aligned}$$ $\begin{array}{c}\lambda C+\mu (\text{Id}-C)\text{approximately 1-projectionally factors through}D,\end{array}$i.e., for all$$\eta > 0$$ $\eta >0$, there exist bounded operatorsA, Bso thatABis the identity operator$${{\,\textrm{Id}\,}}$$ $\text{Id}$,$$\Vert A\Vert \cdot \Vert B\Vert = 1$$ $\Vert A\Vert ·\Vert B\Vert =1$and$$\Vert \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C}) - ADB\Vert < \eta $$ $\Vert \lambda C+\mu (\text{Id}-C)-ADB\Vert <\eta$. Additionally, if$$\mathcal {C}$$ $C$is unbounded onX(Y), then$$\lambda = \mu $$ $\lambda =\mu$and then$${{\,\textrm{Id}\,}}$$ $\text{Id}$either factors throughDor$${{\,\textrm{Id}\,}}-D$$ $\text{Id}-D$. 

   more » « less
2. Rates of convergence for regression with the graph poly-Laplacian

   https://doi.org/10.1007/s43670-023-00075-5  

   Trillos, Nicolás García; Murray, Ryan; Thorpe, Matthew (November 2023, Sampling Theory, Signal Processing, and Data Analysis)

   Abstract In the (special) smoothing spline problem one considers a variational problem with a quadratic data fidelity penalty and Laplacian regularization. Higher order regularity can be obtained via replacing the Laplacian regulariser with a poly-Laplacian regulariser. The methodology is readily adapted to graphs and here we consider graph poly-Laplacian regularization in a fully supervised, non-parametric, noise corrupted, regression problem. In particular, given a dataset$$\{x_i\}_{i=1}^n$$ ${\left\{x_i\right\}}_{i=1}^n$and a set of noisy labels$$\{y_i\}_{i=1}^n\subset \mathbb {R}$$ ${\left\{y_i\right\}}_{i=1}^n\subset R$we let$$u_n{:}\{x_i\}_{i=1}^n\rightarrow \mathbb {R}$$ $u_n:{\left\{x_i\right\}}_{i=1}^n\to R$be the minimizer of an energy which consists of a data fidelity term and an appropriately scaled graph poly-Laplacian term. When$$y_i = g(x_i)+\xi _i$$ $y_i=g\left(x_i\right)+{\xi }_i$, for iid noise$$\xi _i$$ ${\xi }_i$, and using the geometric random graph, we identify (with high probability) the rate of convergence of$$u_n$$ $u_n$togin the large data limit$$n\rightarrow \infty $$ $n\to \infty$. Furthermore, our rate is close to the known rate of convergence in the usual smoothing spline model. 

   more » « less
3. Spherical convex hull of random points on a wedge

   https://doi.org/10.1007/s00208-023-02704-9  

   Besau, Florian; Gusakova, Anna; Reitzner, Matthias; Schütt, Carsten; Thäle, Christoph; Werner, Elisabeth_M (August 2023, Mathematische Annalen)

   Abstract Consider two half-spaces$$H_1^+$$ $H_1^{+}$and$$H_2^+$$ $H_2^{+}$in$${\mathbb {R}}^{d+1}$$ $R^{d+1}$whose bounding hyperplanes$$H_1$$ $H_1$and$$H_2$$ $H_2$are orthogonal and pass through the origin. The intersection$${\mathbb {S}}_{2,+}^d:={\mathbb {S}}^d\cap H_1^+\cap H_2^+$$ $S_{2,+}^d:=S^d\cap H_1^{+}\cap H_2^{+}$is a spherical convex subset of thed-dimensional unit sphere$${\mathbb {S}}^d$$ $S^d$, which contains a great subsphere of dimension$$d-2$$ $d-2$and is called a spherical wedge. Choosenindependent random points uniformly at random on$${\mathbb {S}}_{2,+}^d$$ $S_{2,+}^d$and consider the expected facet number of the spherical convex hull of these points. It is shown that, up to terms of lower order, this expectation grows like a constant multiple of$$\log n$$ $logn$. A similar behaviour is obtained for the expected facet number of a homogeneous Poisson point process on$${\mathbb {S}}_{2,+}^d$$ $S_{2,+}^d$. The result is compared to the corresponding behaviour of classical Euclidean random polytopes and of spherical random polytopes on a half-sphere. 

   more » « less
4. VC-Dimension of Hyperplanes Over Finite Fields

   https://doi.org/10.1007/s00373-025-02909-6  

   Ascoli, Ruben; Betti, Livia; Cheigh, Justin; Iosevich, Alex; Jeong, Ryan; Liu, Xuyan; McDonald, Brian; Milgrim, Wyatt; Miller, Steven_J; Romero_Acosta, Francisco; et al (March 2025, Graphs and Combinatorics)

   Abstract Let$$\mathbb {F}_q^d$$ $F_q^d$be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ $E\subseteq F_q^d$and a fixed nonzero$$t\in \mathbb {F}_q$$ $t\in F_q$, let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ $H_t\left(E\right)=\{h_y:y\in E\}$, where$$h_y:E\rightarrow \{0,1\}$$ $h_y:E\to \{0,1\}$is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ $\{x\in E:x·y=t\}$. Two of the authors, with Maxwell Sun, showed in the case$$d=3$$ $d=3$that if$$|E|\ge Cq^{\frac{11}{4}}$$ $\left|E\right|\ge C{q}^{\frac{11}{4}}$andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ $H_t\left(E\right)$is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ $H_t\left(E\right)$isdwhenever$$E\subseteq \mathbb {F}_q^d$$ $E\subseteq F_q^d$with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ $\left|E\right|\ge C_d{q}^{d-\frac{1}{d-1}}$. 

   more » « less
5. Algorithms for covering multiple submodular constraints and applications

   https://doi.org/10.1007/s10878-022-00874-x  

   Chekuri, Chandra; Inamdar, Tanmay; Quanrud, Kent; Varadarajan, Kasturi; Zhang, Zhao (June 2022, Journal of Combinatorial Optimization)

   Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$ $w:N\to R_{+}$,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$ $f_1,f_2,\dots ,f_r$overNand requirements$$k_1,k_2,\ldots ,k_r$$ $k_1,k_2,\dots ,k_r$the goal is to find a minimum weight subset$$S \subseteq N$$ $S\subseteq N$such that$$f_i(S) \ge k_i$$ $f_i\left(S\right)\ge k_i$for$$1 \le i \le r$$ $1\le i\le r$. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$ $r=1$Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$ $O(log(kr\left)\right)$approximation where$$k = \sum _i k_i$$ $k={\sum }_i{k}_i$and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$ $(1-1/e-\epsilon )$while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$ $O(\frac{1}{ϵ}logr)$in the cost. Second, we consider the special case when each$$f_i$$ $f_i$is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems. 

   more » « less