Construction of Incoherent Dictionaries via Direct Babel Function Minimization

Huan Li, Zhouchen Lin
Proceedings of The 10th Asian Conference on Machine Learning, PMLR 95:598-613, 2018.

Abstract

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^2\mbox{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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v95-li18e, title = {Construction of Incoherent Dictionaries via Direct Babel Function Minimization}, author = {Li, Huan and Lin, Zhouchen}, booktitle = {Proceedings of The 10th Asian Conference on Machine Learning}, pages = {598--613}, year = {2018}, editor = {Zhu, Jun and Takeuchi, Ichiro}, volume = {95}, series = {Proceedings of Machine Learning Research}, month = {14--16 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v95/li18e/li18e.pdf}, url = {https://proceedings.mlr.press/v95/li18e.html}, abstract = {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^2\mbox{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.} }
Endnote
%0 Conference Paper %T Construction of Incoherent Dictionaries via Direct Babel Function Minimization %A Huan Li %A Zhouchen Lin %B Proceedings of The 10th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jun Zhu %E Ichiro Takeuchi %F pmlr-v95-li18e %I PMLR %P 598--613 %U https://proceedings.mlr.press/v95/li18e.html %V 95 %X 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^2\mbox{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.
APA
Li, H. & Lin, Z.. (2018). Construction of Incoherent Dictionaries via Direct Babel Function Minimization. Proceedings of The 10th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 95:598-613 Available from https://proceedings.mlr.press/v95/li18e.html.

Related Material