Mutual coherence in dictionaries and their impact on sparse coding problems
Loading...
Files
Date
2025-02-26
Authors
Κάτσος, Παναγιώτης
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Sparse coding (Compressed Sensing) is a signal processing technique widely used in various fields of modern science and technology. Its applications span multiple domains, including: Wireless telecommunications, Medical signal processing, Audio, speech, image, and video processing, among others. Signals that have a sparse representation can be reconstructed using an appropriate basis (dictionary) from a small number of measurements. Based on this principle, it becomes evident that dictionary design plays a crucial role in sparse coding and, consequently, in the efficient reconstruction of signals. Classical algorithms in the literature focus on the coherence of dictionaries (mutual coherence) to achieve sparse representations of data. For this reason, many researchers have concentrated on developing methods that construct dictionaries by optimizing criteria such as:Mutual coherence, Average coherence. These methods primarily rely on iterative gradient descent techniques, singular value decomposition (SVD) analysis and Linear Programming techniques. In this masters thesis, we conduct a comprehensive study on the role of mutual coherence in sparse coding by utilizing classical sparse representation techniques, such as Basis Pursuit and Orthogonal Matching Pursuit (OMP). Furthermore, we perform a systematic evaluation of state-of-the-art dictionary design methods, assessing their effectiveness in minimizing coherence and improving signal reconstruction performance. As part of our contributions, we propose an alternative formulation of the dictionary optimization problem, which recasts the conventional frame design approach into a Linear Programming (LP) problem. This reformulation provides a novel perspective on mutual coherence minimization and enables a direct comparison with existing iterative optimization methods. Moreover, we introduce a Sequential Quadratic Programming (SQP)-based approach to address the optimization problem efficiently. Through extensive numerical simulations, we assess the performance of these formulation against well-established dictionary learning techniques, providing insights into their computational complexity, coherence minimization capabilities, and scalability.
Description
Keywords
Sparse coding, Dictionary learning, Linear programming