When in Doubt, SWAP: High-Dimensional Sparse Recovery from Correlated Measurements
We consider the problem of accurately estimating a high-dimensional sparse vector using a small number of linear measurements that are contaminated by noise. It is well known that standard computationally tractable sparse recovery algorithms, such as the Lasso, OMP, and their various extensions, perform poorly when the measurement matrix contains highly correlated columns. We develop a simple greedy algorithm, called SWAP, that iteratively swaps variables until a desired loss function cannot be decreased any further. SWAP is surprisingly effective in handling measurement matrices with high correlations. We prove that SWAP can easily be used as a wrapper around standard sparse recovery algorithms for improved performance. We theoretically quantify the statistical guarantees of SWAP and complement our analysis with numerical results on synthetic and real data.
This paper proposes a wrapper called SWAP that can be 
      applied around a given sparse solution with the potential for improving 
      the likelihood that the maximally sparse (L0 norm) solution can be found. 
      The procedure involves simply optimally swapping pairs of basis vectors in 
      the sense of minimizing a quadratic penalty term. Both theoretical and 
      empirical evidence are provided indicating that this proposal is more 
      robust to dictionary correlations, which may disrupt convex L1-norm-based 
      algorithms like Lasso or greedy techniques such as OMP or CoSaMP. At a 
      high level, the basic idea seems to be that, while most existing methods 
      are sensitive to correlations among 2k or more dictionary columns (where k 
      is the sparsity level of the L0 solution), the proposed SWAP algorithm is 
      only sensitive to such correlations among 2k or fewer, a less stringent 
      condition for guaranteeing successful sparse recovery. One of the 
      primary advantages of SWAP is that it can be applied to potentially 
      improve the estimation quality of a solution produced by virtually any 
      sparse estimation technique. Moreover, under somewhat technical conditions 
      which depend on the cardinality and support of the maximally sparse 
      solution, it may conceivably recovery the true support even when other 
      algorithms fail. Although concrete examples where this provably occurs are 
      lacking (more on this below), in general I found the paper to be mostly 
      well-composed and thought-provoking. A significant downside though 
      is that the formal recovery results depend on deploying SWAP while 
      actually knowing the cardinality k of the optimal solution, which is 
      generally not known in practice, and it is unclear how the algorithm will 
      degrade when k is not available in advance. This is unlike the Lasso, 
      where provable recovery guarantees can be derived without such explicit 
      knowledge. As a second potential limitation, while it may well be true 
      that SWAP has not been formally proposed previously, there is likely a 
      very practical reason for this. Namely, SWAP is not scalable to large 
      problem sizes unlike other greedy selection methods like OMP. More 
      concretely, in the realistic scenario when number of measurements n, basis 
      vectors p, and the sparsity level k all increase linearly, the complexity 
      of a single SWAP iteration would increase by at least the cube of the 
      common scale factor. In contrast, other greedy algorithms scale no more 
      than quadratically. Moreover, the convergence rate is still an open 
      question. In all of the experiments provided, the sparsity k was very low, 
      only k=20 or smaller. In such a restricted scenario, it is not surprising 
      that a few basis functions swaps here and there can lead to considerable 
      improvement relative to baseline, both in estimation quality (support 
      recovery percentage) and convergence rate. It would be interesting however 
      to see how SWAP works in a more realistic higher-dimensional setting. 
      The setup for Theorem 4.1, the primary result, takes a bit of time 
      to digest and could possibly be augmented by a more comprehensive, 
      intuitive description beyond the few remarks provided. In particular, it 
      would be helpful to give an example dictionary such that conditions (7) 
      and (8) are satisfied, while the corresponding conditions for Lasso, etc., 
      are not. Note that in the experimental results section, a block diagonal 
      dictionary is proposed; however, it would appear that with such a 
      dictionary it is unlikely that (7) and possibly (8) would be satisfied in 
      this case. Assuming d > 1 (meaning the initial solution given to SWAP 
      has more than one inactive element per the definition in the paper), there 
      will generally always be a subset S of k atoms such that all of the 
      associated inactive elements in this subset will be correlated with an 
      active element in the subset. This is true because any active atom has a 
      group of highly correlated atoms by construction, most of which are not 
      part of the active set. Consequently, unlike analogous recovery results 
      pertaining to Lasso (which incidently do not require any knowledge of the 
      true support pattern, only the value of k), it is much less intuitive 
      exactly where the advantage of SWAP lies, and specific dictionary 
      structures where Lasso provably fails and SWAP provably succeeds. In other 
      words, it seems that the situation described on line 205 is frequently in 
      fact true for correlated dictionaries, and hence some further comment is 
      warranted. Additionally, because the paper is primary of a 
      technical nature, with involved proof techniques of the flavor developed 
      in various other statistical settings, e.g. references [5,8–10,12], it 
      would be helpful from a reviewing standpoint to give a few words regarding 
      which aspects of the proof most resemble existing work and which aspects 
      are the most novel. While I investigated parts of the proof in the lengthy 
      supplementary section, I admittedly did not check it all (note that on 
      line 492 of the supplementary, I believe the first instance of "active" 
      should be switched to "inactive"). Other comments: * I 
      would be curious how well a slight, far more computationally tractable 
      modification of SWAP might perform. Specifically, what if instead of 
      searching for the best pair of atoms to swap, you instead first find the 
      best atom to add, then find the best atom to delete, and iterate back and 
      forth? At the very least, the complexity would decrease drastically, 
      although it is not clear how the theoretical and empirical results might 
      change. * Is there a mistake on line 221 regarding the relative 
      vector sizes? It would appear generally that max(d+1,k) = k in all of the 
      most interesting cases (basically except when the estimated support has no 
      overlap at all with the true support, such that d = k). Perhaps the max is 
      supposed to be a min? * Is there a factor of 16 missing on line 
      269 of the paper? * Line 291 seems to imply that the number of 
      measurements n need only scale logarithmically with k (and p-k). How is 
      this possible, since doesn't this mean that n could be smaller than k at 
      some point? Additionally, do these claims regarding the number of 
      measurements assume that conditions (7) and (8) are somehow automatically 
      satisfied asymptotically? Because it would seem that it would all depend 
      on how a correlated dictionary is that is being expanded in high 
      dimensions, which has not been formally defined in the paper unless I'm 
      missing something obvious. * On line 310 it does it mean that only 
      four active variables are assigned to the same block (and the rest 
      randomly dispersed), or alternatively that, given k = 20, five different 
      blocks each have four active variables?