Structured Sparsity Optimization With Non-Convex Surrogates of l_2,0-Norm: A Unified Algorithmic Framework

Area of Science:

• Optimization
• Signal Processing
• Machine Learning

Background:

• Traditional methods for structured sparse objectives (l2,0-norm) use convex surrogates (l2,1-norm), leading to performance gaps.
• Existing approximations may not fully capture the benefits of structured sparsity.

Purpose of the Study:

• To present a general optimization framework for structured sparsity that overcomes limitations of convex surrogates.
• To develop a robust algorithm for solving non-convex structured sparse recovery problems.
• To demonstrate the framework's applicability in diverse real-world scenarios.

Main Methods:

• A general optimization framework accommodating various surrogate functions, including non-convex ones.
• A fixed-point algorithm guaranteeing global optimality and super-linear convergence for non-convex problems.
• Formulation and relaxation of optimization problems for outlier pursuit, supervised feature selection, and structured dictionary learning.

Main Results:

• The proposed framework achieves superior recovery results compared to traditional methods.
• The fixed-point algorithm converges efficiently to the global optimum.
• Extensive experiments show the framework's effectiveness and efficiency on synthetic and real-world data.

Conclusions:

• The novel optimization framework effectively harnesses structured sparsity, outperforming existing methods.
• The developed algorithm provides a reliable solution for complex non-convex structured sparse recovery problems.
• The framework demonstrates broad applicability and significant potential in data analysis and machine learning.