Search

Abstract: The block Kaczmarz method is an iterative scheme for solving overdetermined least-squares problems. At each step, the algorithm projects the current iterate onto the solution space of a subset of the constraints. This paper describes a block Kaczmarz algorithm that uses a randomized control scheme to choose the subset at each step. This algorithm is the first block Kaczmarz method with an (expected) linear rate of convergence that can be expressed in terms of the geometric properties of the matrix and its submatrices. The analysis reveals that the algorithm is most effective when it is given a good row paving of the matrix, a partition of the rows into well-conditioned blocks. The operator theory literature provides detailed information about the existence and construction of good row pavings. Together, these results yield an efficient block Kaczmarz scheme that applies to many overdetermined least-squares problem. [Copyright &y& Elsevier]

Abstract: An equiangular tight frame (ETF) is a matrix that has unit-norm columns and orthogonal rows of norm . Its key property is that the absolute inner products between pairs of columns are (i) identical and (ii) as small as possible. ETFs have applications in communications, coding theory, and sparse approximation. Numerical experiments indicate that ETFs arise for very few pairs (d, N), and it is an important challenge to develop restrictions on the pairs for which they can exist. This article uses field theory to provide detailed conditions on real and complex ETFs. In particular, it describes restrictions on harmonic ETFs, a specific type of complex ETF that appears in applications. Finally, the article offers empirical evidence that these conditions are sharp or nearly sharp, especially in the real case. [Copyright &y& Elsevier]