Structured Matrix Recovery via the Generalized Dantzig Selector
In recent years, structured matrix recovery problems have gained considerable attention for its real world applications, such as recommender systems and computer vision. Much of the existing work has focused on matrices with low-rank structure, and limited progress has been made on matrices with other types of structure. In this paper we present non-asymptotic analysis for estimation of generally structured matrices via the generalized Dantzig selector based on sub-Gaussian measurements. We show that the estimation error can always be succinctly expressed in terms of a few geometric measures such as Gaussian widths of suitable sets associated with the structure of the underlying true matrix. Further, we derive general bounds on these geometric measures for structures characterized by unitarily invariant norms, a large family covering most matrix norms of practical interest. Examples are provided to illustrate the utility of our theoretical development.
The paper under review consider recovery of general structured measurements with the Danzig selector from linear measurements.   Specifically, the paper assumes measurements y_i = < \theta,X_i > + w_i, where X_i are measurement matrices and w_i is a scalar corresponding to noise.  The paper considers the estimator   arg min_\theta R(\theta)  subject to R*(\sum_i ( < \theta,X_i > - y_i ) X_i ) \leq \lambda_n,  where R is an arbitrary matrix norm and R* is its dual.   The paper assumes sub-Gaussian measurement matrices and sub-Gaussian noise, which is a very general setup.   The main result of the paper appears to be what is stated in the text in the first paragraph of Section 5:   If the number of measurements is larger than the squared Gaussian width of the tangent cone with respect to the norm R, then the recovery error is bounded in a certain sense.  This is similar to [Cor. 3.3, 10], which pertains to Gaussian measurements and bounded noise. 
1. In essence the paper provides generalizations of known results: It shows that matrices with structure (e.g., low rank) can be recovered from sub-Gaussian measurements.  What appears to be new is the very general problem setup.  Specifically the paper considers general norms R as well as the measurement matrices and the noise are assumed to be sub-Gaussian instead of Gaussian, for which corresponding results are already available.   However, several works have shown already that Gaussian measurement matrices can be substituted by sub-Gaussian measurement matrices; this is essentially a consequence of theory developed in [10] and Gordan's lemma holding for more general than Gaussian matrices. See for example the work by Dirksen ``Dimensionality Reduction with Subgaussian Matrices" for a concrete example of this line of work.   While I understand that it is not easy to prove such results, the paper would need to explain if and why the results are novel with respect to the literature mentioned above, and why and if they provide a substantial improvement with respect to the state of the art.   It might be for example that there are interesting choices of the norm R that are relevant and not covered by results in the literature yet.   2. After having read the introduction several times, it is not clear what the main contribution and the specific problem considered of the paper is. Specifically, the paper does not elaborate what it means with ``generally structured matrices''. As a consequence, it is not clear whether the problem of recovering ``generally structured matrices'' includes interesting examples beyond the usual low rank models covered by the literature already.   3. In general the writing could be improved significantly; the paper contains many typos (e.g., only on the bottom of page 5: Lemma 2 ends without colon, Base-> Based; supplementary -> supplementary material; etc), and more importantly, the statements have to be combined by the reader himself to obtain the most interesting results of the paper.   Specifically, the current structure is the following:  Section 2 starts with a deterministic recovery condition (Theorem 1) that expresses the estimation error in Frobenius norm in terms of the geometry of the tangent cone at \theta*.   Section 4 bounds quantities relevant for the deterministic recovery condition in Theorem 1 for sub-Gaussian measurement matrices and sub-Gaussian noise.   Finally, in Section 5, the paper states in words what the results in Section 2 and 4 combined yield, and some implications. This is one of the most interesting conclusions of the paper, and appears to be the main result of the paper (see above).   It would be great if the paper would be reorganized so that a main result, e.g., what is stated in the first paragraph of Section 5, would be stated and discussed in detail early in the paper.  Moreover, additional explanations on how this result improves the state of the art, and pointing to special case already treated by the literature (e.g. [Cor. 3.3, 10]) would be helpful.   As it is now, Section 4 contains several theorems that bound and relate quantities relevant for the deterministic recovery condition. E.g., Theorem 4 lower bounds the condition in terms of the Gaussian width of the tangent cone (note that this result uses generic chaining and is stated for subgaussian matrices; however for Gaussian matrices this is well know, see [10]) Only combined with Theorem 1 those statements yield a recovery result; if this is what the paper sets out to do, then it would be significantly more clear if all those Theorems 3-7 were stated as lemmas, and only one central Theorem were stated and discussed.     Minor comments:   1. Sec. 2: ``The recovery bound assumes not knowledge of R'': It is not clear what is meant with this statement. The recovery bound depends on the norm R, and the convex program assumes knowledge of R.   2. Sec. 4 ``X_i's are copies of a random vector'': Those are matrices.