Functional Analysis (math.FA)

  • PDF
    Feature hashing, also known as \em the hashing trick, introduced by Weinberger et al. (2009), is one of the key techniques used in scaling-up machine learning algorithms. Loosely speaking, feature hashing uses a random sparse projection matrix $A : \mathbb{R}^n \to \mathbb{R}^m$ (where $m \ll n$) in order to reduce the dimension of the data from $n$ to $m$ while approximately preserving the Euclidean norm. Every column of $A$ contains exactly one non-zero entry, equals to either $-1$ or $1$. Weinberger et al. showed tail bounds on $\|Ax\|_2^2$. Specifically they showed that for every $\varepsilon, \delta$, if $\|x\|_{\infty} / \|x\|_2$ is sufficiently small, and $m$ is sufficiently large, then $$\Pr[ \; | \;\|Ax\|_2^2 - \|x\|_2^2\; | < \varepsilon \|x\|_2^2 \;] \ge 1 - \delta \;.$$ These bounds were later extended by Dasgupta \etal (2010) and most recently refined by Dahlgaard et al. (2017), however, the true nature of the performance of this key technique, and specifically the correct tradeoff between the pivotal parameters $\|x\|_{\infty} / \|x\|_2, m, \varepsilon, \delta$ remained an open question. We settle this question by giving tight asymptotic bounds on the exact tradeoff between the central parameters, thus providing a complete understanding of the performance of feature hashing. We complement the asymptotic bound with empirical data, which shows that the constants "hiding" in the asymptotic notation are, in fact, very close to $1$, thus further illustrating the tightness of the presented bounds in practice.
  • PDF
    In this paper, we define and study Gevrey spaces in a subelliptic setting, that is, associated with a Hörmander family of vector fields and their corresponding sub-Laplacian. We show some natural relations between the various Gevrey spaces in this setting on general manifolds, and more particular properties on Lie groups with polynomial growth of the volume. In the case of the Heisenberg group and of $SU(2)$, we show that all our descriptions coincide.
  • PDF
    For generators of Markov semigroups, it is shown how bounds on the density of states near zero lead to algebraic decay rates. These rates follow from a so-called "weak Poincaré inequality". These results are applied to the heat semigroup, where the optimal decay rate is recovered, as well as to the semigroup generated by the fractional Laplacian.
  • PDF
    We study relations between spectra of two operators that are connected to each other through some intertwining conditions. As application we obtain new results on the spectra of multiplication operators on $B(\cl H)$ relating it to the spectra of the restriction of the operators to the ideal $\mathcal C_2$ of Hilbert-Schmidt operators. We also solve one of the problems, posed in [B.Magajna, Proc. Amer. Math. Soc, 141 2013, 1349-1360] about the positivity of the spectrum of multiplication operators with positive operator coefficients when the coefficients on one side commute. Using the Wiener-Pitt phenomena we show that the spectrum of a multiplication operator with normal coefficients satisfying the Haagerup condition might be strictly larger than the spectrum of its restriction to $\mathcal C_2$.
  • PDF
    Approximation processes in the reproducing kernel Hilbert space associated to a continuous kernel on the unit sphere $S^m$ in the Euclidean space $\mathbb{R}^{m+1}$ are known to depend upon the Mercer's expansion of the compact and self-adjoint $L^2(S^m)$-operator associated to the kernel. The estimation of the Kolmogorov $n$-th width of the unit ball of the reproducing kernel Hilbert space in $L^2(S^m)$ and the identification of the so-called optimal subspace usually suffice. These Kolmogorov widths can be computed through the eigenvalues of the integral operator associated to the kernel. This paper provides sharp upper bounds for the Kolmogorov widths in the case in which the kernel satisfies an abstract Hölder condition. In particular, we follow the opposite direction usually considered in the literature, that is, we estimate the widths from decay rates for the sequence of eigenvalues of the integral operator.
  • PDF
    Let $G$ be a countable discrete amenable group, and $\Lambda$ be a strongly connected finite $k$-graph. If $(G,\Lambda)$ is a pseudo free and locally faithful self-similar action which satisfies the finite-state condition, then the structure of the KMS simplex of the C*-algebra $\O_{G,\Lambda}$ associated to $(G,\Lambda)$ is described: it is either empty or affinely isomorphic to the tracial state space of the C*-algebra of the periodicity group $\Per_{G,\Lambda}$ of $(G,\Lambda)$, depending on whether the Perron-Frobenius eigenvector of $\Lambda$ preserves the $G$-action. As applications of our main results, we also exhibit several classes of important examples.
  • PDF
    We consider a magnetostatic problem in a 3D "cylindrical" domain of Koch type. We prove existence and uniqueness results for both the fractal and pre-fractal problems and we investigate the convergence of the pre-fractal solutions to the limit fractal one. We consider the numerical approximation of the pre-fractal problems via FEM and we prove a priori error estimates. Some numerical simulations are also shown. Our long term motivation includes studying problems that appear in quantum physics in fractal domains.
  • PDF
    We first develop a theory of conditional expectations for random variables with values in a complete metric space $M$ equipped with a contractive barycentric map $\beta$, and then give convergence theorems for martingales of $\beta$-conditional expectations. We give the Birkhoff ergodic theorem for $\beta$-values of ergodic empirical measures and provide a description of the ergodic limit function in terms of the $\beta$-conditional expectation. Moreover, we prove the continuity property of the ergodic limit function by finding a complete metric between contractive barycentric maps on the Wasserstein space of Borel probability measures on $M$. Finally, the large derivation property of $\beta$-values of i.i.d. empirical measures is obtained by applying the Sanov large deviation principle.
  • PDF
    In this expository paper we answer two fundamental questions concerning discrete magnetic Schrödinger operator associated with weighted graphs. We discuss when formal expressions of such operators give rise to self-adjoint operators, i.e., when they have self-adjoint restrictions. If such self-adjoint restrictions exist, we explore when they are unique.
  • PDF
    We construct a family of quantum scalar fields over a $p-$adic spacetime which satisfy $p-$adic analogues of the Gå rding--Wightman axioms. Most of the axioms can be formulated the same way in both, the Archimedean and non-Archimedean frameworks; however, the axioms depending on the ordering of the background field must be reformulated, reflecting the acausality of $p-$adic spacetime. The $p-$adic scalar fields satisfy certain $p-$adic Klein-Gordon pseudo-differential equations. The second quantization of the solutions of these Klein-Gordon equations corresponds exactly to the scalar fields introduced here.

Recent comments

Marco Tomamichel Jun 25 2013 05:41 UTC

This is a very nice solution to our (very recent) conjecture. We have in the meantime solved the remaining conjectures and will post an update soon.