- 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.
- May 23 2018 math.FA arXiv:1805.08667v1In 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.
- 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.
- May 23 2018 math.FA arXiv:1805.08553v1We 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$.
- May 23 2018 math.FA arXiv:1805.08476v1Approximation 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.
- 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.
- 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.