The Kaczmarz method is an iterative method for solving overcomplete linear systems of equations Ax=b. The randomized version of the Kaczmarz method put forth by Strohmer and Vershynin iteratively projects onto a randomly chosen solution space given by a single row of the matrix A and converges exponentially in expectation to the solution of a consistent system. In this paper we analyze two block versions of the method each with a randomized projection, that converge in expectation to the least squares solution of inconsistent systems. Our approach utilizes a paving of the matrix A to guarantee exponential convergence, and suggests that paving yields a significant improvement in performance in certain regimes. The proposed method is an extension of the block Kaczmarz method analyzed by Needell and Tropp and the Randomized Extended Kaczmarz method of Zouzias and Freris. The contribution is thus two-fold; unlike the standard Kaczmarz method, our methods converge to the least-squares solution of inconsistent systems, and by using appropriate blocks of the matrix this convergence can be significantly accelerated. Numerical experiments suggest that the proposed algorithm can indeed lead to advantages in practice.
@cite_18: 
@cite_4: We give an elementary proof of a generalization of Bourgain and Tzafriri’s Restricted Invertibility Theorem, which says roughly that any matrix with columns of unit length and bounded operator norm has a large coordinate subspace on which it is well-invertible. Our proof gives the tightest known form of this result, is constructive, and provides a deterministic polynomial time algorithm for finding the desired subspace.
@cite_41: We extend the invertibility principle of J. Bourgain and L. Tzafriri to operators acting on arbitrary decompositionsid = ∑x j ⊕x j , rather than on the coordinate one. The John's decomposition brings this result to the local theory of Banach spaces. As a consequence, we get a new lemma of Dvoretzky-Rogers type, where the contact points of the unit ball with its maximal volume ellipsoid play a crucial role. We then apply these results to embeddings ofl ∞ k into finite dimensional spaces.
@cite_28: 
@cite_42: 
@cite_39: Let X be a n×p real matrix with coherence μ(X)=maxj≠j′|XjtXj′|. We present a simplified and improved study of the quasi-isometry property for most submatrices of X obtained by uniform column sampling. Our results depend on μ(X), the operator norm ‖X‖ and the dimensions with explicit constants, which improve the previously known values by a large factor. The analysis relies on a tail-decoupling argument, of independent interest, and a recent version of the Non-Commutative Chernoff inequality (NCCI).
@cite_0: Many problems in the theory of sparse approximation require bounds on operator norms of a random submatrix drawn from a fixed matrix. The purpose of this Note is to collect estimates for several different norms that are most important in the analysis of l1 minimization algorithms. Several of these bounds have not appeared in detail.
@cite_45: The main problem investigated in this paper is that of restricted invertibility of linear operators acting on finite dimensionall p -spaces. Our initial motivation to study such questions lies in their applications. The results obtained below enable us to complete earlier work on the structure of complemented subspaces ofL p -spaces which have extremal euclidean distance.
@cite_49: 
@cite_51: This note presents a new proof of an important result due to Bourgain and Tzafriri that provides a partial solution to the Kadison-Singer problem. The result shows that every unit-norm matrix whose entries are relatively small in comparison with its dimension can be paved by a partition of constant size. That is, the coordinates can be partitioned into a constant number of blocks so that the restriction of the matrix to each block of coordinates has norm less than one half. The original proof of Bourgain and Tzafriri involves a long, delicate calculation. The new proof relies on the systematic use of symmetrization and (noncommutative) Khinchin inequalities to estimate the norms of some random matrices.
@cite_47: 
@cite_10: We prove a normalized version of the restricted invertibility principle obtained by Spielman-Srivastava. Applying this result, we get a new proof of the proportional Dvoretzky-Rogers factorization theorem recovering the best current estimate. As a consequence, we also recover the best known estimate for the Banach-Mazur distance to the cube: the distance of every n-dimensional normed space from ^n is at most (2n)^(5 6). Finally, using tools from the work of Batson-Spielman-Srivastava, we give a new proof for a theorem of Kashin-Tzafriri on the norm of restricted matrices.
@cite_11: Given a fixed matrix, the problem of column subset selection requests a column submatrix that has favorable spectral properties. Most research from the algorithms and numerical linear algebra communities focuses on a variant called rank-revealing QR , which seeks a well-conditioned collection of columns that spans the (numerical) range of the matrix. The functional analysis literature contains another strand of work on column selection whose algorithmic implications have not been explored. In particular, a celebrated result of Bourgain and Tzafriri demonstrates that each matrix with normalized columns contains a large column submatrix that is exceptionally well conditioned. Unfortunately, standard proofs of this result cannot be regarded as algorithmic. This paper presents a randomized, polynomial-time algorithm that produces the submatrix promised by Bourgain and Tzafriri. The method involves random sampling of columns, followed by a matrix factorization that exposes the well-conditioned subset of columns. This factorization, which is due to Grothendieck, is regarded as a central tool in modern functional analysis. The primary novelty in this work is an algorithm, based on eigenvalue minimization, for constructing the Grothendieck factorization. These ideas also result in a novel approximation algorithm for the @math norm of a matrix, which is generally NP -hard to compute exactly. As an added bonus, this work reveals a surprising connection between matrix factorization and the famous maxcut semidefinite program.
Construction of pavings has been studied for quite some time now, and most early results rely on random selection. The guarantee of lower and upper paving bounds has been derived by Bourgain and Tzafriri @cite_45 and Kashin and Tzafriri @cite_49 , respectively. Simultaneous guarantees were later derived by Bourgain and Tzafriri @cite_42 with suboptimal dependence on the matrix norm. Recently, Spielman and Srivastava @cite_4 and Youssef @cite_10 provided simple proofs of the results from @cite_45 and @cite_49 , respectively. Vershynin @cite_41 and Srivastava @cite_18 extend the paving results to general matrices with arbitrary row norms; see also @cite_10 @cite_47 . Proposition follows from the work of Vershynin @cite_28 and Tropp @cite_11 , and is attributed to the seminal work of Bourgain and Tzafriri @cite_45 @cite_42 . For particular classes of matrices, the paving can even be obtained from a random partition of the rows with high probability. This is proved by Tropp @cite_0 using ideas from @cite_42 @cite_51 , and is refined in @cite_39 .