Scaling clustering algorithms to massive data sets is a challenging task.
Recently, several successful approaches based on data summarization methods,
such as coresets and sketches, were proposed. While these techniques provide
provably good and small summaries, they are inherently problem dependent - the
practitioner has to commit to a fixed clustering objective before even
exploring the data. However, can one construct small data summaries for a wide
range of clustering problems simultaneously? In this work, we affirmatively
answer this question by proposing an efficient algorithm that constructs such
one-shot summaries for k-clustering problems while retaining strong theoretical
guarantees.

本文介绍了一种构建用于 k 聚类问题的一次性数据汇总摘要的有效算法，从而同时为范围广泛的聚类问题构建小型数据摘要且具备强有力的理论保证。

一次性核心集：k - 聚类的情形

One-Shot Coresets: The Case of k-Clustering

Geometric data summarization has become an essential tool in both geometric
approximation algorithms and where geometry intersects with big data problems.
In linear or near-linear time large data sets can be compressed into a summary,
and then more intricate algorithms can be run on the summaries whose results
approximate those of the full data set. Coresets and sketches are the two most
important classes of these summaries. We survey five types of coresets and
sketches: shape-fitting, density estimation, high-dimensional vectors,
high-dimensional point sets / matrices, and clustering.

本文主要介绍了几种几何数据压缩的技术，即将大数据集压缩为概要信息，以在更短的时间内运行算法并近似完整数据集的结果。其中包括 shape-fitting、density estimation、高维向量、高维点集 / 矩阵和聚类等五种核心集合和草图的类型。

核心集和草图

Coresets and Sketches

Retrieving 3D models from 2D human sketches has received considerable
attention in the areas of graphics, image retrieval, and computer vision.
Almost always in state of the art approaches a large amount of "best views" are
computed for 3D models, with the hope that the query sketch matches one of
these 2D projections of 3D models using predefined features.
We argue that this two stage approach (view selection -- matching) is
pragmatic but also problematic because the "best views" are subjective and
ambiguous, which makes the matching inputs obscure. This imprecise nature of
matching further makes it challenging to choose features manually. Instead of
relying on the elusive concept of "best views" and the hand-crafted features,
we propose to define our views using a minimalism approach and learn features
for both sketches and views. Specifically, we drastically reduce the number of
views to only two predefined directions for the whole dataset. Then, we learn
two Siamese Convolutional Neural Networks (CNNs), one for the views and one for
the sketches. The loss function is defined on the within-domain as well as the
cross-domain similarities. Our experiments on three benchmark datasets
demonstrate that our method is significantly better than state of the art
approaches, and outperforms them in all conventional metrics.

该研究提出了一个基于 Siamese 卷积神经网络的方法，将一个 2D 的手绘草图转换为一个 3D 模型，并相比其他先进方法取得了更好的效果。

基于卷积神经网络的基于手绘草图的三维形状检索

Sketch-based 3D Shape Retrieval using Convolutional Neural Networks

In this paper we develop algorithms for approximating matrix multiplication
with respect to the spectral norm. Let A\in{\RR^{n\times m}} and B\in\RR^{n
\times p} be two matrices and \eps>0. We approximate the product A^\top B using
two down-sampled sketches, \tilde{A}\in\RR^{t\times m} and
\tilde{B}\in\RR^{t\times p}, where t\ll n such that \norm{\tilde{A}^\top
\tilde{B} - A^\top B} \leq \eps \norm{A}\norm{B} with high probability. We use
two different sampling procedures for constructing \tilde{A} and \tilde{B}; one
of them is done by i.i.d. non-uniform sampling rows from A and B and the other
is done by taking random linear combinations of their rows. We prove bounds
that depend only on the intrinsic dimensionality of A and B, that is their rank
and their stable rank; namely the squared ratio between their Frobenius and
operator norm. For achieving bounds that depend on rank we employ standard
tools from high-dimensional geometry such as concentration of measure arguments
combined with elaborate \eps-net constructions. For bounds that depend on the
smaller parameter of stable rank this technology itself seems weak. However, we
show that in combination with a simple truncation argument is amenable to
provide such bounds. To handle similar bounds for row sampling, we develop a
novel matrix-valued Chernoff bound inequality which we call low rank
matrix-valued Chernoff bound. Thanks to this inequality, we are able to give
bounds that depend only on the stable rank of the input matrices...

本文提出了一种利用两种不同抽样方法进行矩阵乘法，以逼近具有谱范数的矩阵，从而得出理论上的界限。