We consider the problem of sparse coding, where each sample consists of a
sparse linear combination of a set of dictionary atoms, and the task is to
learn both the dictionary elements and the mixing coefficients. Alternating
minimization is a popular heuristic for sparse coding, where the dictionary and
the coefficients are estimated in alternate steps, keeping the other fixed.
Typically, the coefficients are estimated via $\ell_1$ minimization, keeping
the dictionary fixed, and the dictionary is estimated through least squares,
keeping the coefficients fixed. In this paper, we establish local linear
convergence for this variant of alternating minimization and establish that the
basin of attraction for the global optimum (corresponding to the true
dictionary and the coefficients) is $\order{1/s^2}$, where $s$ is the sparsity
level in each sample and the dictionary satisfies RIP. Combined with the recent
results of approximate dictionary estimation, this yields provable guarantees
for exact recovery of both the dictionary elements and the coefficients, when
the dictionary elements are incoherent.

本文探讨了关于稀疏编码的问题，其中每个样本由一组字典原子的稀疏线性组合组成，任务是同时学习字典元素和混合系数。我们考虑交替最小化法来处理此问题，并建立了该方法的局部线性收敛性质；同时还证明了全局最优解的吸引盆的尺寸为 $\order {1/s^2}$，其中 $s$ 为每个样本的稀疏度，字典满足有限鲁棒性原则 (RIP)。与最近的近似字典估计结果相结合，可以为完全恢复字典元素和系数提供可证明的保证，当字典元素不相干时。

通过交替最小化学习稀疏使用的过完备字典

Learning Sparsely Used Overcomplete Dictionaries via Alternating  Minimization

Consider a movie recommendation system where apart from the ratings
information, side information such as user's age or movie's genre is also
available. Unlike standard matrix completion, in this setting one should be
able to predict inductively on new users/movies. In this paper, we study the
problem of inductive matrix completion in the exact recovery setting. That is,
we assume that the ratings matrix is generated by applying feature vectors to a
low-rank matrix and the goal is to recover back the underlying matrix.
Furthermore, we generalize the problem to that of low-rank matrix estimation
using rank-1 measurements. We study this generic problem and provide conditions
that the set of measurements should satisfy so that the alternating
minimization method (which otherwise is a non-convex method with no convergence
guarantees) is able to recover back the {\em exact} underlying low-rank matrix.
In addition to inductive matrix completion, we show that two other low-rank
estimation problems can be studied in our framework: a) general low-rank matrix
sensing using rank-1 measurements, and b) multi-label regression with missing
labels. For both the problems, we provide novel and interesting bounds on the
number of measurements required by alternating minimization to provably
converges to the {\em exact} low-rank matrix. In particular, our analysis for
the general low rank matrix sensing problem significantly improves the required
storage and computational cost than that required by the RIP-based matrix
sensing methods \cite{RechtFP2007}. Finally, we provide empirical validation of
our approach and demonstrate that alternating minimization is able to recover
the true matrix for the above mentioned problems using a small number of
measurements.

本论文研究了基于用户年龄或电影类型等内容信息，预测新用户或新电影评分的电影推荐系统，提出了使用低秩矩阵加特征向量生成评分矩阵的方法，并探讨了使用基于排名的测量值进行低秩矩阵恢复的问题和方法，并在具体三个问题上进行了应用和实验验证。

可证明的归纳矩阵补全

Provable Inductive Matrix Completion

Phase retrieval problems involve solving linear equations, but with missing
sign (or phase, for complex numbers) information. More than four decades after
it was first proposed, the seminal error reduction algorithm of (Gerchberg and
Saxton 1972) and (Fienup 1982) is still the popular choice for solving many
variants of this problem. The algorithm is based on alternating minimization;
i.e. it alternates between estimating the missing phase information, and the
candidate solution. Despite its wide usage in practice, no global convergence
guarantees for this algorithm are known. In this paper, we show that a
(resampling) variant of this approach converges geometrically to the solution
of one such problem -- finding a vector $\mathbf{x}$ from
$\mathbf{y},\mathbf{A}$, where $\mathbf{y} =
\left|\mathbf{A}^{\top}\mathbf{x}\right|$ and $|\mathbf{z}|$ denotes a vector
of element-wise magnitudes of $\mathbf{z}$ -- under the assumption that
$\mathbf{A}$ is Gaussian.
Empirically, we demonstrate that alternating minimization performs similar to
recently proposed convex techniques for this problem (which are based on
"lifting" to a convex matrix problem) in sample complexity and robustness to
noise. However, it is much more efficient and can scale to large problems.
Analytically, for a resampling version of alternating minimization, we show
geometric convergence to the solution, and sample complexity that is off by log
factors from obvious lower bounds. We also establish close to optimal scaling
for the case when the unknown vector is sparse. Our work represents the first
theoretical guarantee for alternating minimization (albeit with resampling) for
any variant of phase retrieval problems in the non-convex setting.

本文研究相位恢复问题的非凸情况，证明了一种改进的交替最小化算法的几何收敛性，同时提供了样本复杂度的分析，包括稀疏向量的最优缩放。

交替最小化算法用于相位恢复

Phase Retrieval using Alternating Minimization

Alternating minimization represents a widely applicable and empirically
successful approach for finding low-rank matrices that best fit the given data.
For example, for the problem of low-rank matrix completion, this method is
believed to be one of the most accurate and efficient, and formed a major
component of the winning entry in the Netflix Challenge.
In the alternating minimization approach, the low-rank target matrix is
written in a bi-linear form, i.e. $X = UV^\dag$; the algorithm then alternates
between finding the best $U$ and the best $V$. Typically, each alternating step
in isolation is convex and tractable. However the overall problem becomes
non-convex and there has been almost no theoretical understanding of when this
approach yields a good result.
In this paper we present first theoretical analysis of the performance of
alternating minimization for matrix completion, and the related problem of
matrix sensing. For both these problems, celebrated recent results have shown
that they become well-posed and tractable once certain (now standard)
conditions are imposed on the problem. We show that alternating minimization
also succeeds under similar conditions. Moreover, compared to existing results,
our paper shows that alternating minimization guarantees faster (in particular,
geometric) convergence to the true matrix, while allowing a simpler analysis.

本文首次理论分析了交替极小化算法在矩阵完成和矩阵感知问题中的表现，证明了在满足某些条件下，该算法可以快速收敛到真实矩阵，同时具有更简单的分析方法。