High Dimensional Structured Superposition Models
High dimensional superposition models characterize observations using parameters which can be written as a sum of multiple component parameters, each with its own structure, e.g., sum of low rank and sparse matrices, sum of sparse and rotated sparse vectors, etc. In this paper, we consider general superposition models which allow sum of any number of component parameters, and each component structure can be characterized by any norm. We present a simple estimator for such models, give a geometric condition under which the components can be accurately estimated, characterize sample complexity of the estimator, and give high probability nonasymptotic bounds on the componentwise estimation error. We use tools from empirical processes and generic chaining for the statistical analysis, and our results, which substantially generalize prior work on superposition models, are in terms of Gaussian widths of suitable sets.
The authors study superposition models and their recovery from noisy linear samples. They analyze the scenario where we observe linear samples of linear superpositions of k structured parameters and obtain robust estimation conditions based on standard tools such as restricted strong convexity.
The authors study superposition models and their recovery from noisy linear samples. This topic is very well studied in recent years and there are multiple high impact papers characterizing the behavior of such models. In this sense, the technical contribution is not novel enough, and in particular, many of the results can be derived with already existing tools or are straightforward.  Most importantly, though, the claims of this paper are misleading. Authors first state Eq 3 which would be a great result for the high-dimensional statistics literature. Here, we have $k$ structured parameters, and once we demix them, the total estimation error grows as the worst parameter \max_i omega(C_i). This is great because, what I would expect is " \sum_i omega(C_i)" which is k times worse.  In reality, we can never achieve \max_i omega(C_i) for reasonable problems of interest in the demixing (or superposition) literature. In particular, the proposed SC condition (9) have a additional sqrt(k) constant on the left side for any reasonable demixing assumption. The reason is that as soon as we introduce a mild randomness to one of the parameters, the cones C_i are approximately orthogonal and l2 norm will not linearly add up.   The only interesting problem for which SC condition holds for a constant is when all the parameters are same!  I don't think that the authors are intentionally hiding the impact of k (maybe they didn't notice). However, as it stands, this paper claims to reduce a quantity that grows as k to log(k) which is misleading. I recommend them they emphasize the impact of k cleanly (e.g. at Eq 3 as well as when \rho is first introduced.