We study the fundamental limits of matching pursuit, or the pure greedy
algorithm, for approximating a target function by a sparse linear combination
of elements from a dictionary. When the target function is contained in the
variation space corresponding to the dictionary, many impressive works over the
past few decades have obtained upper and lower bounds on the convergence rate
of matching pursuit, but they do not match. The main contribution of this paper
is to close this gap and obtain a sharp characterization of the performance of
matching pursuit. We accomplish this by improving the existing lower bounds to
match the best upper bound. Specifically, we construct a worst case dictionary
which proves that the existing upper bound cannot be improved. It turns out
that, unlike other greedy algorithm variants, the converge rate is suboptimal
and is determined by the solution to a certain non-linear equation. This
enables us to conclude that any amount of shrinkage improves matching pursuit
in the worst case.

该研究研究了通过字典中的元素的稀疏线性组合逼近目标函数的纯贪心算法 matching pursuit 的基本极限和收敛速率，发现与其他贪心算法变体不同的是，它的收敛速率是次优的，并由特定的非线性方程的解决方案确定，任何收缩量都会在最坏情况下改善 matching pursuit。

匹配追踪的快速收敛率

Sharp Convergence Rates for Matching Pursuit

Learning continuous representations of discrete objects such as text, users,
movies, and URLs lies at the heart of many applications including language and
user modeling. When using discrete objects as input to neural networks, we
often ignore the underlying structures (e.g., natural groupings and
similarities) and embed the objects independently into individual vectors. As a
result, existing methods do not scale to large vocabulary sizes. In this paper,
we design a simple and efficient embedding algorithm that learns a small set of
anchor embeddings and a sparse transformation matrix. We call our method Anchor
& Transform (ANT) as the embeddings of discrete objects are a sparse linear
combination of the anchors, weighted according to the transformation matrix.
ANT is scalable, flexible, and end-to-end trainable. We further provide a
statistical interpretation of our algorithm as a Bayesian nonparametric prior
for embeddings that encourages sparsity and leverages natural groupings among
objects. By deriving an approximate inference algorithm based on Small Variance
Asymptotics, we obtain a natural extension that automatically learns the
optimal number of anchors instead of having to tune it as a hyperparameter. On
text classification, language modeling, and movie recommendation benchmarks, we
show that ANT is particularly suitable for large vocabulary sizes and
demonstrates stronger performance with fewer parameters (up to 40x compression)
as compared to existing compression baselines.

本文提出了一种名为 “Anchor & Transform (ANT)” 的简单而高效的嵌入算法，它能够处理大容量的离散对象嵌入，通过从中学习少量的锚点和稀疏的转换矩阵，将对象嵌入成为锚点的稀疏线性组合。这种算法是可扩展、灵活和端到端训练的。同时，研究人员还将其解释为一种贝叶斯非参数先验，旨在促进稀疏性并利用对象间的自然分组关系，我们在多个基准测试中发现，ANT 特别适用于大词汇量，相较于现有压缩基线提供了更强的性能表现（高达 40 倍压缩的低参数）。

锚定 & 转换：为大词汇量学习稀疏嵌入

Anchor & Transform: Learning Sparse Embeddings for Large Vocabularies

One challenge that remains open in 3D deep learning is how to efficiently
represent 3D data to feed deep networks. Recent works have relied on volumetric
or point cloud representations, but such approaches suffer from a number of
issues such as computational complexity, unordered data, and lack of finer
geometry. This paper demonstrates that a mesh representation (i.e. vertices and
faces to form polygonal surfaces) is able to capture fine-grained geometry for
3D reconstruction tasks. A mesh however is also unstructured data similar to
point clouds. We address this problem by proposing a learning framework to
infer the parameters of a compact mesh representation rather than learning from
the mesh itself. This compact representation encodes a mesh using free-form
deformation and a sparse linear combination of models allowing us to
reconstruct 3D meshes from single images. In contrast to prior work, we do not
rely on silhouettes and landmarks to perform 3D reconstruction. We evaluate our
method on synthetic and real-world datasets with very promising results. Our
framework efficiently reconstructs 3D objects in a low-dimensional way while
preserving its important geometrical aspects.

本文提出了一种使用基于网格的表示来捕捉三维重构任务中的细粒度几何信息的学习框架，它使用自由形变和稀疏线性组合的紧凑网格表示来重建三维物体，相比之前的工作，我们不依赖于轮廓和标记来进行三维重建，并在合成和真实数据集上进行了很有前途的实验结果验证。