# Online Orthogonal Dictionary Learning Based on Frank-Wolfe Method

arXiv: https://arxiv.org/abs/2103.01484 · HTML: https://mlsanity.com/paper/2103.01484/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 74 references that are in the map.
- First posted on arXiv 2 Mar 2021.

## Builds on (most cited first, 13 of 13)

- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture](https://mlsanity.com/paper/1511.03607/) (2015)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [Stochastic Frank-Wolfe Methods for Nonconvex Optimization](https://mlsanity.com/paper/1607.08254/) (2016)
- [Variance-Reduced and Projection-Free Stochastic Optimization](https://mlsanity.com/paper/1602.02101/) (2016)
- [Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method](https://mlsanity.com/paper/1511.04777/) (2015)
- [Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap](https://mlsanity.com/paper/1711.01660/) (2017)
- [Subgradient Descent Learns Orthogonal Dictionaries](https://mlsanity.com/paper/1810.10702/) (2018)
- [Approximating Orthogonal Matrices with Effective Givens Factorization](https://mlsanity.com/paper/1905.05796/) (2019)
- [Complete Dictionary Learning via ℓp-norm Maximization](https://mlsanity.com/paper/2002.10043/) (2020)
- [Blind Data Detection in Massive MIMO via ℓ3-norm Maximization over the Stiefel Manifold](https://mlsanity.com/paper/2004.12301/) (2020)
- [Energy Disaggregation via Deep Temporal Dictionary Learning](https://mlsanity.com/paper/1809.03534/) (2018)

## Abstract (arXiv)

Dictionary learning is a widely used unsupervised learning method in signal processing and machine learning. Most existing works of dictionary learning are in an offline manner. There are mainly two offline ways for dictionary learning. One is to do an alternative optimization of both the dictionary and the sparse code; the other way is to optimize the dictionary by restricting it over the orthogonal group. The latter one is called orthogonal dictionary learning which has a lower complexity implementation, hence, it is more favorable for lowcost devices. However, existing schemes on orthogonal dictionary learning only work with batch data and can not be implemented online, which is not applicable for real-time applications. This paper proposes a novel online orthogonal dictionary scheme to dynamically learn the dictionary from streaming data without storing the historical data. The proposed scheme includes a novel problem formulation and an efficient online algorithm design with convergence analysis. In the problem formulation, we relax the orthogonal constraint to enable an efficient online algorithm. In the algorithm design, we propose a new Frank-Wolfe-based online algorithm with a convergence rate of O(ln t/t^(1/4)). The convergence rate in terms of key system parameters is also derived. Experiments with synthetic data and real-world sensor readings demonstrate the effectiveness and efficiency of the proposed online orthogonal dictionary learning scheme.