Catalog

See 3 catalog results
Physical and digital books, media, journals, archives, and databases.
Results include

  1. Code supplement for "The Noise-Sensitivity Phase Transition in Spectral Group Synchronization Over Compact Groups"

    Romanov, Elad
    March 2018

    In Group Synchronization, one attempts to find a collection of unknown group elements from noisy measurements of their pairwise differences. Several important problems in vision and data analysis reduce to group synchronization over various compact groups. Spectral Group Synchronization is a commonly used, robust algorithm for solving group synchronization problems, which relies on diagonalization of a block matrix whose blocks are matrix representations of the measured pairwise differences. Assuming uniformly distributed measurement errors, we present a rigorous analysis of the accuracy and noise sensitivity of spectral group synchronization algorithms over any compact group, up to the rounding error. We identify a Baik-Ben Arous-P\'ech\'e type phase transition in the noise level, beyond which spectral group synchronization necessarily fails. Below the phase transition, spectral group synchronization succeeds in recovering the unknown group elements, but its performance deteriorates with the noise level. We provide asymptotically exact formulas for the accuracy of spectral group synchronization below the phase transition, up to the rounding error. We also provide a consistent risk estimate, allowing practitioners to estimate the method's accuracy from available measurements.

  2. Code and Data Supplement for "Near-optimal matrix recovery from random linear measurements"

    Romanov, Elad
    April 1, 2017

    In matrix recovery from random linear measurements, one is interested in recovering an unknown $M$-by-$N$ matrix $X_0$ from $n<MN$ measurements $y_i=Tr(A_i^\T X_0)$ where each $A_i$ is an $M$-by-$N$ measurement matrix with i.i.d random entries, $i=1,\ldots,n$. We present a novel matrix recovery algorithm, based on approximate message passing, which iteratively applies an optimal singular value shrinker -- a nonconvex nonlinearity tailored specifically for matrix estimation. Our algorithm often converges exponentially fast, offering a significant speedup over previously suggested matrix recovery algorithms, such as iterative solvers for Nuclear Norm Minimization (NNM). It is well known that there is recovery tradeoff between the information content of the object $X_0$ to be recovered (specifically, its matrix rank $r$) and the number of linear measurements $n$ from which recovery is to be attempted. The precise tradeoff between $r$ and $n$, beyond which recovery by a given algorithm becomes possible, traces the so-called phase transition curve of that algorithm in the $(r,n)$ plane. The phase transition curve of our algorithm is noticeably better than that of NNM. Interestingly, it is close to the information-theoretic lower bound for the minimal number of measurements needed for matrix recovery, making it not only the fastest algorithm known, but also near-optimal in terms of the matrices it successfully recovers.

  3. Code Supplement for "ScreeNOT: Exact MSE-Optimal Singular Value Thresholding in Correlated Noise"

    Donoho, David L.
    September 29, 2020; October 2020

    We derive a formula for optimal hard thresholding of the singular value decomposition in the presence of correlated additive noise; although it nominally involves unobservables, we show how to apply it even where the noise covariance structure is not a-priori known or is not independently estimable. The proposed method, which we call ScreeNOT, is a mathematically solid alternative to Cattell's ever-popular but vague Scree Plot heuristic from 1966. ScreeNOT has a surprising oracle property: it typically achieves exactly, in large finite samples, the lowest possible MSE for matrix recovery, on each given problem instance - i.e. the specific threshold it selects gives exactly the smallest achievable MSE loss among all possible threshold choices for that noisy dataset and that unknown underlying true low rank model. The method is computationally efficient and robust against perturbations of the underlying covariance structure. Our results depend on the assumption that the singular values of the noise have a limiting empirical distribution of compact support; this model, which is standard in random matrix theory, is satisfied by many models exhibiting either cross-row correlation structure or cross-column correlation structure, and also by many situations where there is inter-element correlation structure. Simulations demonstrate the effectiveness of the method even at moderate matrix sizes. The paper is supplemented by ready-to-use software packages implementing the proposed algorithm.

Guides

Course- and topic-based guides to collections, tools, and services.
No guide results found... Try a different search

Library website

Library info; guides & content by subject specialists
No website results found... Try a different search

Exhibits

Digital showcases for research and teaching.
No exhibits results found... Try a different search

EarthWorks

Geospatial content, including GIS datasets, digitized maps, and census data.
No earthworks results found... Try a different search

More search tools

Tools to help you discover resources at Stanford and beyond.