Title: High Dimensional Structured Superposition Models,
Abstract: 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 non-asymptotic 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.