The Permuted Striped Block Model and its Factorization - Algorithms with Recovery Guarantees. Article Swipe

MAKE IMPACT

Michael Murray , Jared Tanner · YOU? · · 2020 · Open Access ·

We introduce a novel class of matrices which are defined by the factorization $\textbf{Y} :=\textbf{A}\textbf{X}$, where $\textbf{A}$ is an $m \times n$ wide sparse binary matrix with a fixed number $d$ nonzeros per column and $\textbf{X}$ is an $n \times N$ sparse real matrix whose columns have at most $k$ nonzeros and are $\textit{dissociated}$. Matrices defined by this factorization can be expressed as a sum of $n$ rank one sparse matrices, whose nonzero entries, under the appropriate permutations, form striped blocks - we therefore refer to them as Permuted Striped Block (PSB) matrices. We define the $\textit{PSB data model}$ as a particular distribution over this class of matrices, motivated by its implications for community detection, provable binary dictionary learning with real valued sparse coding, and blind combinatorial compressed sensing. For data matrices drawn from the PSB data model, we provide computationally efficient factorization algorithms which recover the generating factors with high probability from as few as $N =O\left(\frac{n}{k}\log^2(n)\right)$ data vectors, where $k$, $m$ and $n$ scale proportionally. Notably, these algorithms achieve optimal sample complexity up to logarithmic factors.

Type

preprint

Language

en

Landing Page

https://arxiv.org/abs/2004.05094

OA Status

green

References

28

Related Works

20

OpenAlex ID

https://openalex.org/W3015701845

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W3015701845

Canonical identifier for this work in OpenAlex

Title

The Permuted Striped Block Model and its Factorization - Algorithms with Recovery Guarantees.

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2020

Year of publication

Publication date

2020-04-10

Full publication date if available

Authors

Michael Murray, Jared Tanner

List of authors in order

Landing page

https://arxiv.org/abs/2004.05094

Publisher landing page

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/abs/2004.05094

Direct OA link when available

Concepts

Factorization, Combinatorics, Logarithm, Binary number, Mathematics, Block (permutation group theory), Sparse matrix, Matrix (chemical analysis), Rank (graph theory), Class (philosophy), Block structure, Discrete mathematics, Algorithm, Computer science, Arithmetic, Physics, Mathematical analysis, Gaussian, Artificial intelligence, Materials science, Estimator, Quantum mechanics, Statistics, Composite material

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

References (count)

28

Number of works referenced by this work

Related works (count)

20

Other works algorithmically related by OpenAlex

Full payload