Let
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 polyLaplacian regulariser. The methodology is readily adapted to graphs and here we consider graph polyLaplacian regularization in a fully supervised, nonparametric, noise corrupted, regression problem. In particular, given a dataset
 Award ID(s):
 2005797
 NSFPAR ID:
 10475993
 Publisher / Repository:
 Springer Science + Business Media
 Date Published:
 Journal Name:
 Sampling Theory, Signal Processing, and Data Analysis
 Volume:
 21
 Issue:
 2
 ISSN:
 27305716
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract be an elliptically fibered$$X\rightarrow {{\mathbb {P}}}^1$$ $X\to {P}^{1}$K 3 surface, admitting a sequence of Ricciflat metrics collapsing the fibers. Let$$\omega _{i}$$ ${\omega}_{i}$V be a holomorphicSU (n ) bundle overX , stable with respect to . Given the corresponding sequence$$\omega _i$$ ${\omega}_{i}$ of Hermitian–Yang–Mills connections on$$\Xi _i$$ ${\Xi}_{i}$V , we prove that, ifE is a generic fiber, the restricted sequence converges to a flat connection$$\Xi _i_{E}$$ ${\Xi}_{i}{}_{E}$ . Furthermore, if the restriction$$A_0$$ ${A}_{0}$ is of the form$$V_E$$ ${V}_{E}$ for$$\oplus _{j=1}^n{\mathcal {O}}_E(q_j0)$$ ${\oplus}_{j=1}^{n}{O}_{E}({q}_{j}0)$n distinct points , then these points uniquely determine$$q_j\in E$$ ${q}_{j}\in E$ .$$A_0$$ ${A}_{0}$ 
Abstract Approximate integer programming is the following: For a given convex body
, either determine whether$$K \subseteq {\mathbb {R}}^n$$ $K\subseteq {R}^{n}$ is empty, or find an integer point in the convex body$$K \cap {\mathbb {Z}}^n$$ $K\cap {Z}^{n}$ which is$$2\cdot (K  c) +c$$ $2\xb7(Kc)+c$K , scaled by 2 from its center of gravityc . Approximate integer programming can be solved in time while the fastest known methods for exact integer programming run in time$$2^{O(n)}$$ ${2}^{O\left(n\right)}$ . So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point$$2^{O(n)} \cdot n^n$$ ${2}^{O\left(n\right)}\xb7{n}^{n}$ can be found in time$$x^* \in (K \cap {\mathbb {Z}}^n)$$ ${x}^{\ast}\in (K\cap {Z}^{n})$ , provided that the$$2^{O(n)}$$ ${2}^{O\left(n\right)}$remainders of each component for some arbitrarily fixed$$x_i^* \mod \ell $$ ${x}_{i}^{\ast}\phantom{\rule{0ex}{0ex}}mod\phantom{\rule{0ex}{0ex}}\ell $ of$$\ell \ge 5(n+1)$$ $\ell \ge 5(n+1)$ are given. The algorithm is based on a$$x^*$$ ${x}^{\ast}$cuttingplane technique , iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a new$$2^{O(n)}n^n$$ ${2}^{O\left(n\right)}{n}^{n}$asymmetric approximate Carathéodory theorem that might be of interest on its own. Our second method concerns integer programming problems in equationstandard form . Such a problem can be reduced to the solution of$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$ $Ax=b,0\le x\le u,\phantom{\rule{0ex}{0ex}}x\in {Z}^{n}$ approximate integer programming problems. This implies, for example that$$\prod _i O(\log u_i +1)$$ ${\prod}_{i}O(log{u}_{i}+1)$knapsack orsubsetsum problems withpolynomial variable range can be solved in time$$0 \le x_i \le p(n)$$ $0\le {x}_{i}\le p\left(n\right)$ . For these problems, the best running time so far was$$(\log n)^{O(n)}$$ ${(logn)}^{O\left(n\right)}$ .$$n^n \cdot 2^{O(n)}$$ ${n}^{n}\xb7{2}^{O\left(n\right)}$ 
Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground set
N , a weight function ,$$w: N \rightarrow \mathbb {R}_+$$ $w:N\to {R}_{+}$r monotone submodular functions over$$f_1,f_2,\ldots ,f_r$$ ${f}_{1},{f}_{2},\dots ,{f}_{r}$N and requirements the goal is to find a minimum weight subset$$k_1,k_2,\ldots ,k_r$$ ${k}_{1},{k}_{2},\dots ,{k}_{r}$ such that$$S \subseteq N$$ $S\subseteq N$ for$$f_i(S) \ge k_i$$ ${f}_{i}\left(S\right)\ge {k}_{i}$ . We refer to this problem as$$1 \le i \le r$$ $1\le i\le r$MultiSubmodCover and it was recently considered by HarPeled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260 HarPeled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$ $r=1$MultiSubmodCover generalizes the wellknown Submodular Set Cover problem (SubmodSC ), and it can also be easily reduced toSubmodSC . A simple greedy algorithm gives an approximation where$$O(\log (kr))$$ $O(log(kr\left)\right)$ 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 for$$k = \sum _i k_i$$ $k={\sum}_{i}{k}_{i}$MultiSubmodCover that covers each constraint to within a factor of while incurring an approximation of$$(11/e\varepsilon )$$ $(11/e\epsilon )$ in the cost. Second, we consider the special case when each$$O(\frac{1}{\epsilon }\log r)$$ $O(\frac{1}{\u03f5}logr)$ is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover ($$f_i$$ ${f}_{i}$PartialSC ), 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 highlevel model and the lens of submodularity in addressing this class of covering problems. 
For each odd integer
$n \geq 3$ , we construct a rank3 graph$\Lambda _n$ with involution$\gamma _n$ whose real$C^*$ algebra$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda _n, \gamma _n)$ is stably isomorphic to the exotic Cuntz algebra$\mathcal E_n$ . This construction is optimal, as we prove that a rank2 graph with involution$(\Lambda ,\gamma )$ can never satisfy$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )\sim _{ME} \mathcal E_n$ , and Boersema reached the same conclusion for rank1 graphs (directed graphs) in [Münster J. Math.10 (2017), pp. 485–521, Corollary 4.3]. Our construction relies on a rank1 graph with involution$(\Lambda , \gamma )$ whose real$C^*$ algebra$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )$ is stably isomorphic to the suspension$S \mathbb {R}$ . In the Appendix, we show that the$i$ fold suspension$S^i \mathbb {R}$ is stably isomorphic to a graph algebra iff$2 \leq i \leq 1$ . 
Abstract Let
denote the standard Haar system on [0, 1], indexed by$$(h_I)$$ $\left({h}_{I}\right)$ , the set of dyadic intervals and$$I\in \mathcal {D}$$ $I\in D$ denote the tensor product$$h_I\otimes h_J$$ ${h}_{I}\otimes {h}_{J}$ ,$$(s,t)\mapsto h_I(s) h_J(t)$$ $(s,t)\mapsto {h}_{I}\left(s\right){h}_{J}\left(t\right)$ . We consider a class of twoparameter function spaces which are completions of the linear span$$I,J\in \mathcal {D}$$ $I,J\in D$ of$$\mathcal {V}(\delta ^2)$$ $V\left({\delta}^{2}\right)$ ,$$h_I\otimes h_J$$ ${h}_{I}\otimes {h}_{J}$ . This class contains all the spaces of the form$$I,J\in \mathcal {D}$$ $I,J\in D$X (Y ), whereX andY are either the Lebesgue spaces or the Hardy spaces$$L^p[0,1]$$ ${L}^{p}[0,1]$ ,$$H^p[0,1]$$ ${H}^{p}[0,1]$ . We say that$$1\le p < \infty $$ $1\le p<\infty $ is a Haar multiplier if$$D:X(Y)\rightarrow X(Y)$$ $D:X\left(Y\right)\to X\left(Y\right)$ , where$$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}$ , and ask which more elementary operators factor through$$d_{I,J}\in \mathbb {R}$$ ${d}_{I,J}\in R$D . A decisive role is played by theCapon projection given by$$\mathcal {C}:\mathcal {V}(\delta ^2)\rightarrow \mathcal {V}(\delta ^2)$$ $C:V\left({\delta}^{2}\right)\to V\left({\delta}^{2}\right)$ if$$\mathcal {C} h_I\otimes h_J = h_I\otimes h_J$$ $C{h}_{I}\otimes {h}_{J}={h}_{I}\otimes {h}_{J}$ , and$$I\le J$$ $\leftI\right\le \leftJ\right$ if$$\mathcal {C} h_I\otimes h_J = 0$$ $C{h}_{I}\otimes {h}_{J}=0$ , as our main result highlights: Given any bounded Haar multiplier$$I > J$$ $\leftI\right>\leftJ\right$ , there exist$$D:X(Y)\rightarrow X(Y)$$ $D:X\left(Y\right)\to X\left(Y\right)$ such that$$\lambda ,\mu \in \mathbb {R}$$ $\lambda ,\mu \in R$ i.e., for all$$\begin{aligned} \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}\mathcal {C})\text { approximately 1projectionally factors through }D, \end{aligned}$$ $\begin{array}{c}\lambda C+\mu (\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}C)\phantom{\rule{0ex}{0ex}}\text{approximately 1projectionally factors through}\phantom{\rule{0ex}{0ex}}D,\end{array}$ , there exist bounded operators$$\eta > 0$$ $\eta >0$A ,B so thatAB is the identity operator ,$${{\,\textrm{Id}\,}}$$ $\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}$ and$$\Vert A\Vert \cdot \Vert B\Vert = 1$$ $\Vert A\Vert \xb7\Vert B\Vert =1$ . Additionally, if$$\Vert \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}\mathcal {C})  ADB\Vert < \eta $$ $\Vert \lambda C+\mu (\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}C)ADB\Vert <\eta $ is unbounded on$$\mathcal {C}$$ $C$X (Y ), then and then$$\lambda = \mu $$ $\lambda =\mu $ either factors through$${{\,\textrm{Id}\,}}$$ $\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}$D or .$${{\,\textrm{Id}\,}}D$$ $\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}D$