Work on approximate linear algebra has led to efficient distributed and
streaming algorithms for problems such as approximate matrix multiplication,
low rank approximation, and regression, primarily for the Euclidean norm
$\ell_2$. We study other $\ell_p$ norms, which are more robust for $p < 2$, and
can be used to find outliers for $p > 2$. Unlike previous algorithms for such
norms, we give algorithms that are (1) deterministic, (2) work simultaneously
for every $p \geq 1$, including $p = \infty$, and (3) can be implemented in
both distributed and streaming environments. We apply our results to
$\ell_p$-regression, entrywise $\ell_1$-low rank approximation, and approximate
matrix multiplication.

本文研究了适用于不同的 lP 范数的近似线性代数问题，提出了一种同时适用于每个 p ≥ 1 的确定性算法，并将其应用于多种问题，如 lP 回归，逐元素 l1 低秩逼近和近似矩阵乘法。

基于良好条件基础的 Minkowski $p$- 范数流式和分布式摘要

Leveraging Well-Conditioned Bases: Streaming \& Distributed Summaries in  Minkowski $p$-Norms

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.

本文介绍了函数特征哈希技术及其在机器学习中的应用，并给出了在向量维度减少、特征密度、误差范围与置信度之间的紧密渐近界限，并通过实验证明了该界限近似等于 1。

完全理解哈希技巧

Fully Understanding the Hashing Trick

The efficiency of graph-based semi-supervised algorithms depends on the graph
of instances on which they are applied. The instances are often in a vectorial
form before a graph linking them is built. The construction of the graph relies
on a metric over the vectorial space that help define the weight of the
connection between entities. The classic choice for this metric is usually a
distance measure or a similarity measure based on the euclidean norm. We claim
that in some cases the euclidean norm on the initial vectorial space might not
be the more appropriate to solve the task efficiently. We propose an algorithm
that aims at learning the most appropriate vectorial representation for
building a graph on which the task at hand is solved efficiently.

提出了一种算法，旨在学习最适合构建图的向量表示，以便在其上有效地解决半监督算法的任务。