{'fraction_non_alphanumeric': 0.038490885968630775, 'fraction_numerical': 0.008562950402713014, 'mean_word_length': 4.519653720168461, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
SWAGGER: Sparsity Within and Across Groups for General Estimation and Recovery

Penalty functions or regularization terms that promote structured solutions to optimization problems are of great interest in many fields. Proposed in this work is a nonconvex structured sparsity penalty that promotes one-sparsity within arbitrary overlapping groups in a vector. This allows one to enforce mutual exclusivity between components within solutions to optimization problems. We show multiple example use cases (including a total variation variant), demonstrate synergy between it and other regularizers, and propose an algorithm to efficiently solve problems regularized or constrained by the proposed penalty.


I. INTRODUCTION
S PARSITY-promoting regularization is an integral component of modern-day signal processing, optimization and machine learning. The most prevalent method, LASSO [1], uses the 1 norm to promote solutions to optimization problems that have few nonzero coefficients. More recently, within some application domains there has been significant interest in structured sparsity. For instance, group sparsity aims to set entire groups of components within a vector entirely to zero and allow the components in other groups to take on any value [2]. This is often achieved by regularizing with the 2,1 norm over groups, called group LASSO (G-LASSO) [3]. Conversely, there is interest in sparsity penalties that promote intra-group sparsity, that is, ensuring groups within a vector are themselves sparse. Such penalties have been used to great success in areas such as deep learning [4], computer vision [5], [6], and medicine [7], [8]. Previous work in this area includes elitist [9], [10], or exclusive LASSO (E-LASSO) [11] formulations that are convex and result in sparse, disjoint groups, and the nonconvex 'sparsity within and across groups' (SWAG) [12] plus extensions [13] that allow for overlapping groups of components.
We propose here a more general, nonconvex structured sparsity penalty that allows for sparsity within and across overlapping groups for general estimation and recovery (SWAGGER). The SWAGGER formulation encodes mutual exclusivity between pairs of components, or a transform of the components, using an easily constructed sparsity structure matrix. This results in one-sparse groups with minimal bias in the nonzero entries, where bias is typically an unwanted byproduct of using convex sparsity penalties such as elitist LASSO. We demonstrate the utility of SWAGGER in a number of settings, including a novel total variation-style denoising in one and two dimensions and modeling occlusions plus allowing mutually exclusive discretizations in imaging problems. Additionally, we introduce a novel algorithm to efficiently solve problems regularized or constrained by this proposed penalty.

II. PROPOSED PENALTY
We introduce a general structured sparsity penalty for x ∈ R N . For certain choices of the matrix B ∈ R M ×N , where M is any integer, function Φ : R M → R M , and matrix S ∈ R M ×M , this penalizes deviation from a selected form of structured sparsity. Possible prototypes for B include the identity matrix, finite difference matrices, or a transform to a different basis; see Section VII. The function Φ introduces a nonlinearity that helps to bound the penalty from below. We constrain Φ in Prop. 1 below, and examples are discussed in Section V. The matrix S is key, as it encodes the structural sparsity properties. We define S as: where µ ∈ [0, 1] is the strength of exclusivity between a pair of components, Φ(Bx) i and Φ(Bx) j . When µ = 0, there is no exclusivity between the two components. When µ > 0, it indicates that the two components should not be nonzero simultaneously (with the strength of exclusivity increasing with µ). We bound µ in the [0,1] range for convenience and note that any scaling can be absorbed into a multiplicative regularization parameter. Given this interpretation, the diagonal of S will be zero and hence S will typically be indefinite, resulting in nonconvexity. Examples for S are given in Section IV.
In order for the penalty function to be useful in regularizing minimization problems, it must be bounded from below. Prop. 1 provides simple sufficient conditions for this (proof in Appendix A).
where X = diag(sign(x)). The sparsity structure matrix, S, is symmetric and has zeros along its main diagonal. S must be indefinite as it has at least one positive eigenvalue (see [14]) and the sum of the eigenvalues is zero (since the trace of a symmetric matrix is equal to the sum of its eigenvalues and Tr(S) = 0). The Hessian has the same structure and can therefore not be positive semidefinite outside of the trivial case where x = 0. Thus, the penalty is always nonconvex for practical purposes. More analysis of the eigenvalues of matrices of this kind can be found in [15].
We can compare SWAGGER with the convex E-LASSO penalty, which uses the 1 -squared norm to achieve intra-group sparsity. In the case of a one-sparse group (see Section IV-A), we can introduce a modified sparsity matrix, S η = 11 T − ηI, where scalar parameter η ∈ [0, 1] gives us E-LASSO for η = 0 and SWAGGER for η = 1: When η = 1, we see the introduction of the −η x 2 2 term which both de-biases the penalty and also ensures the penalty equals zero when x is one-sparse. For a more general S, the closest convex penalty would be to replace S with S − cI, where c takes on the value of the smallest eigenvalue of S.
Maintaining convexity of a full cost function: There has recently been interest in so called 'convex nonconvex' sparsity regularization where parameters of a nonconvex penalty are set to values that maintain convexity of the full cost function with the data fidelity, e.g., [16]. This is achievable with the SWAGGER penalty, also. Consider the problem of minimizing a cost function of the form 1 2 Ax − y 2 2 + λ|x| T S|x|. One can replace S with S − cI, where c = λ min (S) + 1 2λ λ min (A T A), to achieve nonconvex regularization whilst maintaining the overall convexity of the problem (see derivation in Appendix E). This is only useful when the smallest eigenvalue of A T A is not too small and the regularization strength parameter λ is not too large. The work presented outside of this section is only focused on the use of the unmodified S, but further analysis of the intermediate convexity paradigm may be of interest.

A. Canonical One-sparsity
Define Φ(·) = | · | and B = I. In this case, we obtain This is the 'sparsity within and across overlapping groups' formulation which is introduced in [13]. If we chose S = 11 T − I, where 1 is a column vector of 1s of appropriate dimension, then we see that which is equal to zero for any one-sparse x. Hence, this can be used to promote one-sparse solutions to optimization problems. See Fig. 1(a) for a graphical depiction.

B. Intra-group Sparsity
Define Φ(·) = | · | and B = I. Consider a vector x ∈ R gn where g is a number of groups and n is the number of components in each group. Then, we can promote one-sparsity within each group using S ∈ R gn×gn defined in blocks: where S = 11 T − I n (see Fig. 1(b)). This is now a block-separable problem, equivalent to applying the penalty defined in Section IV-A to different sections of x, i.e., g k=1 |x k | T S|x k |, where k indexes blocks of n components. One use case for this formulation is in modeling occlusions in imaging problems, which we address with an example in Section VII-C.

C. Local Neighborhood Sparsity
Sparsity can be promoted in overlapping local neighborhoods in an ordered sequence of indexes by restricting the nonzeros to a band around the diagonal. This gives a symmetric Toeplitz S (see Fig. 1(c)). For instance, an S with neighbor distance n = 1 is given by For a general neighbor distance n, S is given by where again µ ∈ [0, 1] defines a strength of exclusivity. This imposes local-n-neighborhood one-sparsity, which ensures nonzeros in a solution occur with a minimum separation distance of n indices.

V. CHOICES FOR Φ(·)
The typical choice for Φ(·) is the absolute value | · |. This is the main focus of this paper and admits fast algorithms to result in one-sparse groups with a prescribed structure, with minimal bias. However, we note that other choices can enjoy interesting properties. For instance, using Φ(x) = max(0, x) or Φ(x) = max(0, −x) acts on positive or negative values only, respectively, and meets the condition outlined in Prop. 1. Thus, combining two constraint terms, can result in a solution where only positive correlation is penalized, i.e., a group may contain one positive and negative component, rather than being one-sparse. In [4], exclusive sparsity regularization is used to reduce redundancy in the learned kernels in convolution neural networks. The Φ(·) = max(0, ·) formulation could function as a relaxed approach to this, allowing more degrees of freedom in the filter kernels.
In a case where there can be a large disparity between the size of components within groups in the solution vector, one may wish to impose a nonlinear scaling and use Φ(x) = |x| κ where κ < 1. This reduces the effect of large but possibly incorrect components on other, potentially correct components. This can be seen in use in the two-dimensional local neighborhood total variation example in Section VII-B.

VI. ALGORITHMS
First, we note that when Φ(·) = | · | and B = I, the penalty can be expressed An efficient algorithm to evaluate the proximal operator of the 2 1 norm is available (see Appendix B) [17]. Hence, we can aim to efficiently solve any problem of the form: using a proximal subgradient method (Algorithm 1). This simply requires us to evaluate the (sub)gradient of f (x) − x 2 2 −|x| T (11 T −S−I)|x| and the proximal operator of x 2 1 . In practice, we find the convergence speed of this algorithm is not negatively affected by the use of a subgradient of −|x| T (11 T −S−I)|x| as this term will always aim to push the components of x away from the discontinuity in the gradient at x = 0. Furthermore, in cases with no overlapping groups, this term equals zero.
As this penalty is nonconvex, it is prudent to start with an initial estimate of x that minimizes the data fidelity. Given this, Algorithm 1 outlines the proximal subgradient scheme used to approximately solve the problem in (7) by introducing a Lagrange multiplier λ.
In Algorithm 1, P αλ k is the proximal operator associated with the 2 1 term, · 2 1 , and α is a step size that can be fixed or computed dynamically. There exists an accelerated Algorithm 1 Proximal subgradient method for SWAGGER constrained problems Input: Initial estimate x 0 = arg min x f (x), λ 0 = 0, Output:x 1: while not converged do 2: proximal gradient algorithm that is guaranteed to converge to a stationary point even for nonconvex problems [18], which could be used here also. The algorithm for this is outlined in Appendix C.
When B is not the identity, we can instead solve a problem of the form: using the alternating direction method of multipliers (ADMM) [19], which also uses Algorithm 1 or an accelerated variation thereof at each iteration.

VII. EXAMPLE APPLICATIONS A. Comparison with Other Methods
Three experiments were performed, where measurements y were generated using y = Ax, with white Gaussian noise added to achieved a signal-to-noise radio (SNR) of 25 dB. Matrix A ∈ R 25×60 has random Gaussian entries realized for each trial. The vector x has entries ±U (0.5, 1.5) and is made to fit a specific sparsity structure such that |x| T S|x| ≈ 0 for some S. Details of how this is achieved are presented in Appendix D. In the first experiment, S is fixed and enforces intragroup one-sparsity in ten groups (see Section IV-B), where S ∈ R 6×6 . In the second experiment, a local neighborhood S (see Section IV-C) is used with n = 4. In the third experiment, a new binary S is generated per trial with entries equal to zero or one with 50% probability. We compare the performance of the SWAGGER penalty with other typical sparsity regularizers, both structured and unstructured. The problems solved are of the formx = arg min x The E-LASSO penalty uses a sum of the 1 -squared term over groups. We create one group per row in S, where each group contains the nonzero components in each row (and the diagonal), i.e., g i = { j | S i,j +δ i−j = 1 }. This penalty is not designed for overlapping groups, so the results are poor in the local neighborhood and random S experiments. The pseudoinverse is used in the initialization for the nonconvex penalties,  identified as nonzero, the Jacard index (the intersection of the true support and estimated support divided by the union), and the mean-squared error (MSE) for the components that are nonzero in the ground truth. We see that SWAGGER outperforms the other algorithms in almost every case. It is unsurprising that the unstructured sparsity regularizers (LASSO and p-shrinkage) perform especially poorly in the group S and local neighborhood settings as the true support is not especially sparse overall, whereas SWAGGER is agnostic to the overall sparsity level. Furthermore, the E-LASSO ( 2 1 ) regularizer performs poorly when groups are overlapping, whereas SWAGGER handles this gracefully and without any additional effort required. We also see that the MSE within the correct support is particularly low with SWAGGER, as it implicitly de-biases the solutions (this can be readily seen from the − x 2 2 term in (4)). Of particular interest are the results where λ is tuned to result in the correct sparsity level. The SWAGGER results are particularly favorable in this setting, and this is the most typical use case; it is roughly equivalent to solving the constrained SWAGGER problem in (7) and hence requires no user tuning of the regularization strength.

B. Local Neighborhood Total Variation
The well established total variation (TV) penalty, Dx 1 where multiplying by D takes finite differences, aims to sparsify the changes along the solution vector x. We propose here a local neighborhood total variation (LN-TV) penalty using SWAGGER. LN-TV is achieved by assigning B = D and using an S that promotes sparsity in local neighborhoods as defined in Section IV-C. LN-TV simply ensures that changes in the vector occur at least some minimum distance apart, while allowing changes of any amplitude. This is a prior which suggests the vector is piecewise-constant with a certain minimum segment length. If a typical minimum separation distance between significant changes in a vector is known, LN-TV can outperform TV and Moreau-enhanced TV (a convexnonconvex variation) [21] in a denoising setting, as seen in Fig. 2.
For more general problems, where a piecewise approximation is helpful but the segments do not necessarily have a minimum length well known a priori, the LN-TV penalty can be combined with the traditional TV by solving a problem of the form: where the λ's are parameters that control the strength of the regularization. If A = I, this acts to denoise the input y, but different choices of A can be used to solve deconvolution or deblurring problems, super-resolution, and so on. The addition of the LN-TV term can help avoid the 'staircasing' artefacts that often arise when using TV, and allow for weaker TV regularization, which reduces the bias in the result. We present an example of these favorable effects in Fig. 3. Here, the S matrix used promotes sparsity in Dx within five indices either side of a nonzero component. This formulation is distinct from the one discussed in (7), as instead of a constraint we are using the SWAGGER term as a regularization with a strength prescribed by λ 1 . This allows us to have some more nuance by having a linear ramp from 1 to 0.5 in the band around the diagonal, to make close changes less likely than ones a greater distance away.
We can extend this formulation to a 2D setting also. Using the penalty formulation in (10), we promote horizontal and vertical differences that occur only with some minimal separation distance: where D v and D h are matrices that take finite differences along the vertical columns and horizontal rows, respectively, and S v and S h impose local neighborhood sparsity in the vertical and horizontal directions. We choose Φ(x) = |x| κ which introduces another parameter κ as discussed in Section V. We find that, in general, κ should be kept somewhat smaller than 1 if the initial estimate is especially blurred or noisy, and larger than 1 if there exist hard edges in the initial estimate that should be maintained. For the results shown in Fig. 4, κ = 0.75.

C. Modeling Mutual Surface Occlusions in Non-Line-of-Sight (NLOS) Imaging
The aim of NLOS imaging is to form reconstructions of scenes hidden from the direct line of sight of the observer. Typical methods to achieve this rely on the use of ultra-fast pulsed lasers and time-resolved single photon counting to infer the hidden geometry by measuring round-trip distances [22], [23], [24], [25]. Often, to recover a 3D scene, the hidden area will be discretized into patches or surfaces in some manner. Some of these patches may occlude others: if a surface is actually present in the scene, light coming from others behind it may have no paths to the measurement device. As the discretization is prescribed beforehand, the surfaces occluded by each other are known a priori, and they should be mutually exclusive. Therefore, we can use SWAGGER to ensure that groups of surfaces that occlude one another will be one-sparse in the recovered output. This provides two benefits. Firstly, the recovered output will be physically plausible as surfaces that cannot contribute any light in the measurements will not be present in the solution. Secondly, ensuring this physical constraint is met during the optimization process should lead to better estimations overall. This idea extends to any situation in which an ideal discretization of some physical area, field, etc., involves some mutual exclusivity between elements of the discretization. Typically, to deal with this one may instead use a discretization that is less desirable but avoids or reduces this exclusivity requirement, use post-processing to make the recovery fit the expected structure, or simply ignore it. Using SWAGGER can instead ensure that reconstructions both fit the expected structure prescribed by the underlying physics of the problem, and also enjoy improved estimates due to the knowledge of the structure being used within the optimization procedure. One NLOS imaging system, Edge-Resolved Transient Imaging [26], uses a laser to illuminate the floor at numerous positions in an arc around a vertical edge, such as a doorway, to form a 3D reconstruction of the room beyond. For each measurement position, a histogram of the arrival times of photons reaching a single photon avalanche diode (SPAD) detector is accumulated using time-correlated single photon counting. Each subsequent laser position illuminates more of the hidden scene, and by taking differences between measurement histograms one can recover a noisy measurement containing photon arrivals originating mostly from within a single wedge in the hidden area.
From this difference histogram measurement, one can attempt to fit surfaces to the scene within a wedge, to reconstruct the hidden area. It is assumed that surfaces always start at the ground, extend to a certain height, and are a certain distance from the corner. We can form a reconstruction by solving the following problem: where y is a difference histogram measurement and A is a matrix governing the light transport to and from surfaces at different distances from the edge, and with different heights. Fig. 5 shows reconstructions of a wedge using experimental data from [26]. One reconstruction uses only the x 1 term and no constraints, and a second that includes the SWAGGER constraint. In [26], a Markov chain Monte Carlo (MCMC) method was used to form the reconstructions as it could implicitly include occlusions model and needed to only estimate parameters for a small number of surfaces, rather than use a full scene discretization. Here, we use SWAGGER and a full scene discretization to ensure that surfaces which should occlude those behind them, and vice versa, are accurately modeled. Secondly, it permits us to use a discretization with mutually exclusive elements-surfaces in the same position but with different heights-where only one should be present in the solution. As such, the result is a physically plausible reconstruction, which is quite accurate in support, height, and reflectivity.

VIII. CONCLUSION
Using SWAGGER as a constraint allows one to recover solutions to problems that fit a known sparsity structure, including any number of one-sparse overlapping groups within the solution vector or a transform thereof. This is useful in modeling a wide variety of phenomena, such as occlusions in imaging problems. We illustrate the usefulness of the proposed penalty for some example use cases where, by simply constructing a sparsity structure matrix S, one can ensure estimates fit known hard structured sparsity constraints derived from domain knowledge of the problem. This results in solutions that are both physically plausible and also improved overall. Similarly, SWAGGER can be used as a regularization term with some strength, to promote solutions that fit a sparsity structure whilst allowing more nuance, which gives rise to local-neighborhood total variation. SWAGGER can be readily combined with other priors, regularization terms and constraints to improve estimations. A proximal (sub)gradient algorithm (and accelerated algorithm) have been proposed to quickly solve SWAGGER-constrained and SWAGGERregularized problems.

A. Proof of Proposition 1
Suppose both conditions on Proposition 1 hold. By condition 2), every entry of Φ(Bx) is nonnegative. By condition 1), every entry of S is also nonnegative. Therefore, each entry in the matrix triple product Φ(Bx) T S Φ(Bx) is nonnegative, ensuring that the result is nonnegative.
B. Proximity Operator Algorithm for 2 1 Algorithm 2 reproduces the method from [17] to compute the proximal operator for the 2 1 norm (with O(N log N ) complexity).

C. Accelerated SWAGGER Algorithm
In [18], a monotonic accelerated proximal gradient method is outlined that is guaranteed to converge to a stationary point for nonconvex problems. Algorithm 3 applies this acceleration to Algorithm 1, where α x , α y and α λ are step sizes that can be fixed or computed dynamically with a back-tracking scheme. The convergence proof requires that f (x) is a proper function with Lipschitz continuous gradients (e.g., the least squares loss), and the SWAGGER penalty is proper and lower semicontinuous, which is the case for Φ(x) = |x|.

D. Generating Test Vectors
For the experiments in Section VII-A, we must generate a test vector x for each trial which fits the sparsity structure described by a specific S matrix. To do so we use Algorithm 4, where in Step 4, u j is drawn from the continuous uniform distribution on [0.5, 1.5]. Ax − y 2 2 + λ|x| T S|x| is given by A T A + 2λXSX (where X = diag(sgn(x))). We introduce a term cI to the S matrix: To maintain convexity, we wish to have λ min (A T A + 2λXSX) − 2λc ≥ 0, or equivalently 2λc ≤ λ min (A T A + 2λXSX).
Since A T A and 2λXSX are both Hermitian, by Weyl's inequality [27]. Finally, we note min X λ min (2λXSX)) = 2λ λ min (S), providing us with a bound for the choice of c: c ≤ 1 2λ λ min (A T A) + λ min (S).