{'fraction_non_alphanumeric': 0.023310023310023312, 'fraction_numerical': 0.0034965034965034965, 'mean_word_length': 4.965277777777778, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Solving Basis Pursuit

The problem of finding a minimum ℓ1-norm solution to an underdetermined linear system is an important problem in compressed sensing, where it is also known as basis pursuit. We propose a heuristic optimality check as a general tool for ℓ1-minimization, which often allows for early termination by “guessing” a primal-dual optimal pair based on an approximate support. Moreover, we provide an extensive numerical comparison of various state-of-the-art ℓ1-solvers that have been proposed during the last decade, on a large test set with a variety of explicitly given matrices and several right-hand sides per matrix reflecting different levels of solution difficulty. The results, as well as improvements by the proposed heuristic optimality check, are analyzed in detail to provide an answer to the question which algorithm is the best.