skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Friday, May 16 until 2:00 AM ET on Saturday, May 17 due to maintenance. We apologize for the inconvenience.


Title: Rates of convergence for regression with the graph poly-Laplacian
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$$ { x i } i = 1 n and a set of noisy labels$$\{y_i\}_{i=1}^n\subset \mathbb {R}$$ { y i } i = 1 n R we let$$u_n{:}\{x_i\}_{i=1}^n\rightarrow \mathbb {R}$$ u n : { x i } i = 1 n 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 ( x i ) + ξ i , for iid noise$$\xi _i$$ ξ 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 . Furthermore, our rate is close to the known rate of convergence in the usual smoothing spline model.  more » « less
Award ID(s):
2005797 2236447
PAR ID:
10475993
Author(s) / Creator(s):
; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Sampling Theory, Signal Processing, and Data Analysis
Volume:
21
Issue:
2
ISSN:
2730-5716
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract Using proton–proton collision data corresponding to an integrated luminosity of$$140\hbox { fb}^{-1}$$ 140 fb - 1 collected by the CMS experiment at$$\sqrt{s}= 13\,\text {Te}\hspace{-.08em}\text {V} $$ s = 13 Te V , the$${{{\Lambda }} _{\text {b}}^{{0}}} \rightarrow {{\text {J}/\uppsi }} {{{\Xi }} ^{{-}}} {{\text {K}} ^{{+}}} $$ Λ b 0 J / ψ Ξ - K + decay is observed for the first time, with a statistical significance exceeding 5 standard deviations. The relative branching fraction, with respect to the$${{{\Lambda }} _{\text {b}}^{{0}}} \rightarrow {{{\uppsi }} ({2\textrm{S}})} {{\Lambda }} $$ Λ b 0 ψ ( 2 S ) Λ decay, is measured to be$$\mathcal {B}({{{\Lambda }} _{\text {b}}^{{0}}} \rightarrow {{\text {J}/\uppsi }} {{{\Xi }} ^{{-}}} {{\text {K}} ^{{+}}} )/\mathcal {B}({{{\Lambda }} _{\text {b}}^{{0}}} \rightarrow {{{\uppsi }} ({2\textrm{S}})} {{\Lambda }} ) = [3.38\pm 1.02\pm 0.61\pm 0.03]\%$$ B ( Λ b 0 J / ψ Ξ - K + ) / B ( Λ b 0 ψ ( 2 S ) Λ ) = [ 3.38 ± 1.02 ± 0.61 ± 0.03 ] % , where the first uncertainty is statistical, the second is systematic, and the third is related to the uncertainties in$$\mathcal {B}({{{\uppsi }} ({2\textrm{S}})} \rightarrow {{\text {J}/\uppsi }} {{{\uppi }} ^{{+}}} {{{\uppi }} ^{{-}}} )$$ B ( ψ ( 2 S ) J / ψ π + π - ) and$$\mathcal {B}({{{\Xi }} ^{{-}}} \rightarrow {{\Lambda }} {{{\uppi }} ^{{-}}} )$$ B ( Ξ - Λ π - )
    more » « less
  2. Abstract LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$ [ 0 , 1 ] k where$$k \ge 2$$ k 2 . According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour)$$x_1, x_2, \ldots , x_n$$ x 1 , x 2 , , x n through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ i = 1 n | x i - x i + 1 | k 1 / k c k , where$$|x-y|$$ | x - y | is the Euclidean distance betweenxandy, and$$c_k$$ c k is an absolute constant that depends only onk, where$$x_{n+1} \equiv x_1$$ x n + 1 x 1 . From the other direction, for every$$k \ge 2$$ k 2 and$$n \ge 2$$ n 2 , there existnpoints in$$[0,1]^k$$ [ 0 , 1 ] k , such that their shortest tour satisfies$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$ i = 1 n | x i - x i + 1 | k 1 / k = 2 1 / k · k . For the plane, the best constant is$$c_2=2$$ c 2 = 2 and this is the only exact value known. Bollobás and Meir showed that one can take$$c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ c k = 9 2 3 1 / k · k for every$$k \ge 3$$ k 3 and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$ c k = 2 1 / k · k , for every$$k \ge 2$$ k 2 . Here we significantly improve the upper bound and show that one can take$$c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ c k = 3 5 2 3 1 / k · k or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$ c k = 2.91 k ( 1 + o k ( 1 ) ) . Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$ c 3 2 7 / 6 , which disproves the conjecture for$$k=3$$ k = 3 . Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed. 
    more » « less
  3. Abstract The electricE1 and magneticM1 dipole responses of the$$N=Z$$ N = Z nucleus$$^{24}$$ 24 Mg were investigated in an inelastic photon scattering experiment. The 13.0 MeV electrons, which were used to produce the unpolarised bremsstrahlung in the entrance channel of the$$^{24}$$ 24 Mg($$\gamma ,\gamma ^{\prime }$$ γ , γ ) reaction, were delivered by the ELBE accelerator of the Helmholtz-Zentrum Dresden-Rossendorf. The collimated bremsstrahlung photons excited one$$J^{\pi }=1^-$$ J π = 1 - , four$$J^{\pi }=1^+$$ J π = 1 + , and six$$J^{\pi }=2^+$$ J π = 2 + states in$$^{24}$$ 24 Mg. De-excitation$$\gamma $$ γ rays were detected using the four high-purity germanium detectors of the$$\gamma $$ γ ELBE setup, which is dedicated to nuclear resonance fluorescence experiments. In the energy region up to 13.0 MeV a total$$B(M1)\uparrow = 2.7(3)~\mu _N^2$$ B ( M 1 ) = 2.7 ( 3 ) μ N 2 is observed, but this$$N=Z$$ N = Z nucleus exhibits only marginalE1 strength of less than$$\sum B(E1)\uparrow \le 0.61 \times 10^{-3}$$ B ( E 1 ) 0.61 × 10 - 3  e$$^2 \, $$ 2 fm$$^2$$ 2 . The$$B(\varPi 1, 1^{\pi }_i \rightarrow 2^+_1)/B(\varPi 1, 1^{\pi }_i \rightarrow 0^+_{gs})$$ B ( Π 1 , 1 i π 2 1 + ) / B ( Π 1 , 1 i π 0 gs + ) branching ratios in combination with the expected results from the Alaga rules demonstrate thatKis a good approximative quantum number for$$^{24}$$ 24 Mg. The use of the known$$\rho ^2(E0, 0^+_2 \rightarrow 0^+_{gs})$$ ρ 2 ( E 0 , 0 2 + 0 gs + ) strength and the measured$$B(M1, 1^+ \rightarrow 0^+_2)/B(M1, 1^+ \rightarrow 0^+_{gs})$$ B ( M 1 , 1 + 0 2 + ) / B ( M 1 , 1 + 0 gs + ) branching ratio of the 10.712 MeV$$1^+$$ 1 + level allows, in a two-state mixing model, an extraction of the difference$$\varDelta \beta _2^2$$ Δ β 2 2 between the prolate ground-state structure and shape-coexisting superdeformed structure built upon the 6432-keV$$0^+_2$$ 0 2 + level. 
    more » « less
  4. 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 R + ,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$ f 1 , f 2 , , f r overNand requirements$$k_1,k_2,\ldots ,k_r$$ k 1 , k 2 , , k r the goal is to find a minimum weight subset$$S \subseteq N$$ S N such that$$f_i(S) \ge k_i$$ f i ( S ) k i for$$1 \le i \le r$$ 1 i 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 ( k r ) ) approximation where$$k = \sum _i k_i$$ k = 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 - ε ) while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$ O ( 1 ϵ log r ) 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
  5. 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 H 1 + 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$$ log n . 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