Highly incoherent dictionaries have broad applications in machine learning. Minimizing the mutual coherence is a common intuition to construct incoherent dictionaries in the previous methods. However, as pointed out by Tropp(2004), mutual coherence does not offer a very subtle description and Babel function, as a generalization of mutual coherence, is a more attractive alternative. However, it is much more challenging to optimize. In this work, we minimize the Babel function directly to construct incoherent dictionaries. As far as we know, this is the first work to optimize the Babel function. We propose an augmented Lagrange multiplier based algorithm to solve this nonconvex and nonsmooth problem with the convergence guarantee that every accumulation point is a KKT point. We define a new norm $|X|_{infty,max_p}$ and propose an efficient method to compute its proximal operation with $O(n^2mbox{log}n)$ complexity, which dominates the running time of our algorithm, where $max_p$ means the sum of the largest $p$ elements and $n$ is the number of the atoms. Numerical experiments testify to the advantage of our method.
展开▼
机译：高度不连贯的词典在机器学习中具有广泛的应用。在以前的方法中，构造相互不一致的字典是使相互相干性最小化的一种普遍直觉。但是，正如Tropp（2004）所指出的，互相干并没有提供非常微妙的描述，而Babel函数作为互相干性的概括，是一种更具吸引力的选择。但是，优化更具挑战性。在这项工作中，我们直接最小化Babel函数来构造不连贯的字典。据我们所知，这是优化Babel函数的第一项工作。我们提出了一种基于增强型拉格朗日乘数的算法来解决此非凸且不平滑的问题，并确保每个累加点均为KKT点。我们定义了一个新的规范$ | X | _ { infty，max_p} $，并提出了一种有效的方法来计算其近端运算，复杂度为$ O（n ^ 2 mbox {log} n）$，该方法主导了我们的算法的运行时间，其中$ max_p $表示最大的$ p $元素之和，$ n $是原子数。数值实验证明了我们方法的优势。
展开▼
