Online-Dictionary-Learning-for-Sparse-Coding

Introduction

This repository contains the implementation of the online learning algorithms for sparse coding proposed by Julien Mairal in his paper titled "Online Learning for Matrix Factorization and Sparse Coding".

Sparse coding is a fundamental technique in machine learning and signal processing, with numerous applications in recommendation systems, image processing, and data analysis. While traditional approaches often rely on batch learning algorithms, online learning methods provide a more efficient and scalable solution, enabling real-time updates and adaptivity to changing data streams.

Julien Mairal's paper presents novel online learning algorithms that tackle the challenges of matrix factorization and sparse coding in an online setting. These algorithms not only provide accurate representations of high-dimensional data but also incorporate efficient online updates, making them suitable for large-scale applications.

Results

1. Plotting the Objective Function VS Time (using the online method, batch size of 4, batch size of 10)

• We used 100 iterations on this example.

2. Effect of Increasing the Dictionary Size on the Reconstructed Signal

We study the effect of varying K (number of columns in the dictionary), by plotting the Difference Matrix (between the original dataset X, and reconstructed dataset x_hat)

• This heat map illustrates the absolute difference between the original dataset values, and the entries of the reconstructed matrix.
• The darker the color, the more closer the reconstructed entries to the original ones.
• We just used 5 iterations on this example.

K = 20

1. First Iteration

2. Final (Fifth) Iteration

K = 40

1. First Iteration

2. Final (Fifth) Iteration

K = 60

1. First Iteration

2. Final (Fifth) Iteration

K = 80

1. First Iteration

2. Final (Fifth) Iteration

K = 100

1. First Iteration

2. Final (Fifth) Iteration

Conclusion: The larger the value of K (hence the larger the dictionary), the faster the convergence of the reconstructed signal to the original one.

3. Sparsity

The following two heat maps illustrates the values of both the dictionary $D$ and one of the the sparse coding coefficients columns $\alpha$. It is evident the sparsity in each of them.

Slides

The slides for our presentation about this paper, as a project for the Optimization EEC 494 class, are available here

Thanks

Special thanks to the amazing people that contributed to this project:

1. Pensee Safwat
2. Dyaa Mohamed
3. Abdelrahman Ali
4. Fatma Ezzat
5. Me :)

Contribution

Thank you for your interest in contributing to this research paper code repository! Your contributions can greatly enhance the quality and impact of the project. To contribute, please follow the guidelines outlined below. Bug Reports and Issues

If you encounter any bugs, have questions, or want to report an issue related to the code in this repository, please create a new issue on the GitHub repository page. When creating an issue, provide a clear and concise description of the problem you encountered, along with steps to reproduce it if applicable. This will help us understand and address the issue promptly. Feature Requests

If you have a feature request or an idea for improving the code, please submit a new issue on the GitHub repository. Clearly describe the proposed feature or enhancement, providing as much detail as possible. We appreciate well-documented feature requests that include the rationale behind the suggestion and any potential implementation approaches.