English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Motivated by a sampling problem basic to computational statistical inference,we develop a nearly optimal algorithm for a fundamental problem in spectralgraph theory and numerical analysis. Given an $n\times n$ SDDM matrix ${\bf\mathbf{M}}$, and a constant $-1 \leq p \leq 1$, our algorithm gives efficientaccess to a sparse $n\times n$ linear operator $\tilde{\mathbf{C}}$ such that$${\mathbf{M}}^{p} \approx \tilde{\mathbf{C}} \tilde{\mathbf{C}}^\top.$$ Thesolution is based on factoring ${\bf \mathbf{M}}$ into a product of simple andsparse matrices using squaring and spectral sparsification. For ${\mathbf{M}}$with $m$ non-zero entries, our algorithm takes work nearly-linear in $m$, andpolylogarithmic depth on a parallel machine with $m$ processors. This gives thefirst sampling algorithm that only requires nearly linear work and $n$ i.i.d.random univariate Gaussian samples to generate i.i.d. random samples for$n$-dimensional Gaussian random fields with SDDM precision matrices. Forsampling this natural subclass of Gaussian random fields, it is optimal in therandomness and nearly optimal in the work and parallel complexity. In addition,our sampling algorithm can be directly extended to Gaussian random fields withSDD precision matrices.

Scalable Parallel Factorizations of SDD Matrices and Efficient Sampling for Gaussian Graphical Models