Mark Tygert's homepage

Selected publications

1. William Perkins, Mark Tygert, and Rachel Ward, "Computing the confidence levels for a root-mean-square test of goodness-of-fit," Applied Mathematics and Computation, 217 (22): 9072-9084, 2011: pdf, ps.

   This article points out that, with the now widespread availability of computers, the original χ² statistic for testing goodness-of-fit no longer makes much sense. "χ² and classical exact tests often wildly misreport significance; the remedy lies in computers," available in pdf, is a better place to start for the application-oriented.

2. Edouard Coakley, Vladimir Rokhlin, and Mark Tygert, "A fast randomized algorithm for orthogonal projection," SIAM Journal on Scientific Computing, 33 (2): 849-868, 2011: pdf.

   This article can help accelerate interior-point methods for convex optimization, such as linear programming.

3. Mark Tygert, "Statistical tests for whether a given set of independent, identically distributed draws comes from a specified probability density," Proceedings of the National Academy of Sciences, 107 (38): 16471-16476, 2010: pdf, ps.

   This article modifies and supplements tests of the Kolmogorov-Smirnov type (including Kuiper's).

4. Mark Tygert, "Fast algorithms for spherical harmonic expansions, III," Journal of Computational Physics, 229 (18): 6181-6192, 2010: pdf.

   This article simplifies the precomputations required for computing fast spherical harmonic transforms, complementing the approach taken in the article, "Fast algorithms for spherical harmonic expansions, II," available below.

5. Vladimir Rokhlin, Arthur Szlam, and Mark Tygert, "A randomized algorithm for principal component analysis," SIAM Journal on Matrix Analysis and Applications, 31 (3): 1100-1124, 2009: pdf.

   This article is now out-of-date; instead, please see Nathan Halko's, Per-Gunnar Martinsson's, and Joel Tropp's SIAM Review paper.

6. Franco Woolfe, Edo Liberty, Vladimir Rokhlin, and Mark Tygert, "A fast randomized algorithm for the approximation of matrices," Applied and Computational Harmonic Analysis, 25 (3): 335-366, 2008: pdf.

   This article provides a generally preferable alternative to the classical pivoted "QR" decomposition algorithms (such as Gram-Schmidt or Householder) for the low-rank approximation of arbitrary matrices. Constructing a low-rank approximation is the core step in computing several of the greatest singular values and corresponding singular vectors of a matrix.

7. Vladimir Rokhlin and Mark Tygert, "A fast randomized algorithm for overdetermined linear least-squares regression," Proceedings of the National Academy of Sciences, 105 (36): 13212-13217, 2008: pdf.

   This article provides an algorithm for linear least-squares regression. When the regression is highly overdetermined, the algorithm is more efficient than the classical methods based on "QR" decompositions.

8. Mark Tygert, "Fast algorithms for spherical harmonic expansions, II," Journal of Computational Physics, 227 (8): 4260-4279, 2008: pdf.

   This article provides efficient algorithms for computing spherical harmonic transforms, largely superseding our first article on the subject, "Fast algorithms for spherical harmonic expansions."

9. Edo Liberty, Franco Woolfe, Per-Gunnar Martinsson, Vladimir Rokhlin, and Mark Tygert, "Randomized algorithms for the low-rank approximation of matrices," Proceedings of the National Academy of Sciences, 104 (51): 20167-20172, 2007: pdf.

   This article surveys algorithms for the compression of matrices.

10. Per-Gunnar Martinsson, Vladimir Rokhlin, and Mark Tygert, "A randomized algorithm for the decomposition of matrices," Applied and Computational Harmonic Analysis, 30 (1): 47-68, 2011: pdf.

    This article provides details regarding the survey, "Randomized algorithms for the low-rank approximation of matrices," available above. "A randomized algorithm for the decomposition of matrices" is almost identical to our (better-known) technical report, "A randomized algorithm for the approximation of matrices," from 2006.

11. Per-Gunnar Martinsson, Vladimir Rokhlin, and Mark Tygert, "On interpolation and integration in finite-dimensional spaces of bounded functions," Communications in Applied Mathematics and Computational Science, 1: 133-142, 2006: CAMCoS.

    This article reviews the fact that numerically stable formulae exist for interpolating any linear combination of n bounded functions using the values of the linear combination at a certain collection of n points in the domain of the functions. The article also provides references to algorithms which determine these stable formulae at reasonably small computational expense.

12. Vladimir Rokhlin and Mark Tygert, "Fast algorithms for spherical harmonic expansions," SIAM Journal on Scientific Computing, 27 (6): 1903-1928, 2006: pdf.

    This article is now largely (but not entirely) superseded by the paper, "Fast algorithms for spherical harmonic expansions, II," available above.