Solving OSCAR regularization problems by proximal splitting algorithms
This work addresses a computational bottleneck in sparse regression for scenarios where group structures are unknown, offering a faster method with experimental validation, though it appears incremental as it builds on existing OSCAR and proximal splitting frameworks.
The authors tackled the challenge of applying the OSCAR regularizer, which has a non-trivial proximity operator, by reformulating it as a weighted sorted L1 norm and proposing approximate and grouping proximity operators, enabling the use of proximal splitting algorithms for faster and accurate recovery of group-sparse signals with unknown groups.
The OSCAR (octagonal selection and clustering algorithm for regression) regularizer consists of a L_1 norm plus a pair-wise L_inf norm (responsible for its grouping behavior) and was proposed to encourage group sparsity in scenarios where the groups are a priori unknown. The OSCAR regularizer has a non-trivial proximity operator, which limits its applicability. We reformulate this regularizer as a weighted sorted L_1 norm, and propose its grouping proximity operator (GPO) and approximate proximity operator (APO), thus making state-of-the-art proximal splitting algorithms (PSAs) available to solve inverse problems with OSCAR regularization. The GPO is in fact the APO followed by additional grouping and averaging operations, which are costly in time and storage, explaining the reason why algorithms with APO are much faster than that with GPO. The convergences of PSAs with GPO are guaranteed since GPO is an exact proximity operator. Although convergence of PSAs with APO is may not be guaranteed, we have experimentally found that APO behaves similarly to GPO when the regularization parameter of the pair-wise L_inf norm is set to an appropriately small value. Experiments on recovery of group-sparse signals (with unknown groups) show that PSAs with APO are very fast and accurate.