Mark Tygert's homepage


Selected publications

  1. François Charton, Kristin Lauter, Cathy Li, and Mark Tygert, "An efficient algorithm for integer lattice reduction," SIAM Journal on Matrix Analysis and Applications, 45 (1): 353-367, 2024: pdf.

    This article proposes iterations to polish the results of other algorithms for lattice reduction and demonstrates the polishing on an especially efficient numerical method for Lenstra-Lenstra-Lovász (LLL) reduction in floating-point arithmetic.

  2. Mark Tygert, "Calibration of P-values for calibration and for deviation of a subpopulation from the full population," Advances in Computational Mathematics, 49 (70): 1-22, 2023: pdf.

    This article details calibration of attained significance levels (also known as "P-values") for formal tests of significance related to recently developed analogues of the Kolmogorov-Smirnov and Kuiper metrics. The article also details how to calculate cumulative statistics for data with scores (independent variables in a regression) that may not be unique by instead calculating the cumulative statistics for a weighted data set with scores that are unique by construction.

  3. Imanol Arrieta Ibarra, Paman Gujral, Jonathan Tannen, Mark Tygert, and Cherie Xu, "Metrics of calibration for probabilistic predictions," Journal of Machine Learning Research, 23: 1-54, 2022: pdf.

    This article shows the dramatic superiority of the cumulative metrics of Kuiper and of Kolmogorov and Smirnov over the canonical empirical calibration errors (also known as "estimated calibration errors").

  4. Aaron Defazio, Mark Tygert, Rachel Ward, and Jure Zbontar, "Compressed sensing with a jackknife, a bootstrap, and visualization," Journal of Data Science, Statistics, and Visualisation, 2 (4): 1-29, 2022: pdf.

    This article simulates on a computer what could have happened with measurements that we might have taken but actually did not, given what happened with the measurements that we did in fact make.

  5. Mark Tygert, "A graphical method of cumulative differences between two subpopulations," Journal of Big Data, 8 (158): 1-29, 2021: pdf.

    This article extends an earlier paper, "Cumulative deviation of a subpopulation from the full population," to assessing directly deviation between two subpopulations whose scores are all distinct. The previous paper is preferable when apposite.

  6. Mark Tygert, "Cumulative deviation of a subpopulation from the full population," Journal of Big Data, 8 (117): 1-60, 2021: pdf.

    Graphs of cumulative differences and associated variants of the Kolmogorov-Smirnov and Kuiper statistics help gauge calibration or subpopulation deviation without making any particular tradeoff between resolution and statistical confidence (unlike the traditional reliability diagrams and calibration plots).

  7. Chuan Guo, Awni Hannun, Brian Knott, Laurens van der Maaten, Mark Tygert, and Ruiyu Zhu, "Secure multiparty computations in floating-point arithmetic," Information and Inference: a Journal of the IMA, iaaa038: 1-33, 2021: pdf.

    This article introduces secure multiparty computations for privacy-preserving machine-learning using solely standard floating-point arithmetic, with carefully controlled leakage of information less than the loss of accuracy due to roundoff, all backed by rigorous mathematical proofs of worst-case bounds on information loss and numerical stability in finite-precision arithmetic.

  8. Mark Tygert and Jure Zbontar, "Simulating single-coil MRI from the responses of multiple coils," Communications in Applied Mathematics and Computational Science, 15 (2): 115-127, 2020: pdf.

    This article is strange, yet representative of the curious, idiosyncratic tasks that pay the bills in industry, which often require knowledgeable, special-purpose solutions.

  9. Cinna Wu, Mark Tygert, and Yann LeCun, "A hierarchical loss and its problems when classifying non-hierarchically," PLOS ONE, 14 (12): 1-17, 2019: pdf.

    This article defines an easy-to-use metric of success or figure of merit for classification in which the classes come endowed with a hierarchical taxonomy.

  10. Mark Tygert, "Regression-aware decompositions," Linear Algebra and Its Applications, 565 (6): 208-224, 2019: pdf.

    This article constructs matrix decompositions which leverage simultaneously a single data set's intrinsic low-rank structure as well as low-rank structure in the data's interaction with another data set.

  11. Huamin Li, Yuval Kluger, and Mark Tygert, "Randomized algorithms for distributed computation of principal component analysis and singular value decomposition," Advances in Computational Mathematics, 44 (5): 1651-1672, 2018: pdf.

    This article describes an implementation for Spark of principal component analysis, singular value decomposition, and low-rank approximation.

  12. Arthur Szlam, Andrew Tulloch, and Mark Tygert, "Accurate low-rank approximations via a few iterations of alternating least squares," SIAM Journal on Matrix Analysis and Applications, 38 (2): 425-433, 2017: pdf.

    This article points out that a few iterations of alternating least squares provably suffice to produce nearly optimal spectral- and Frobenius-norm accuracies of low-rank approximations.

  13. Soumith Chintala, Marc'Aurelio Ranzato, Arthur Szlam, Yuandong Tian, Mark Tygert, and Wojciech Zaremba, "Scale-invariant learning and convolutional networks," Applied and Computational Harmonic Analysis, 42 (1): 154-166, 2017: pdf.

    This article develops a classification stage specifically for use with supervised learning in scale-equivariant convolutional networks.

  14. Joan Bruna, Soumith Chintala, Yann LeCun, Serkan Piantino, Arthur Szlam, and Mark Tygert, "A mathematical motivation for complex-valued convolutional networks," Neural Computation, 28 (5): 815-825, 2016: pdf.

    This article embeds multiwavelet absolute values in parametric families of complex-valued convnets.

  15. William Perkins, Mark Tygert, and Rachel Ward, "Some deficiencies of χ2 and classical exact tests of significance," Applied and Computational Harmonic Analysis, 36 (3): 361-386, 2014: pdf.

    This article points out that the Euclidean distance is underutilized in modern statistics.

  16. 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 works out some asymptotic distributions associated with the article, "Some deficiencies of χ2 and classical exact tests of significance," available above.

  17. 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.

  18. 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).

  19. 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.

  20. 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.

  21. 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.

  22. 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.

  23. 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."

  24. 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.

  25. 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.

  26. 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.

  27. 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.