Open Access Publications from the University of California

## Dictionary learning: analysis of spatial gene expression data and local identifiability theory

• Author(s): Wu, Siqi
The biological interpretability of the NMF-derived dictionary motivated us to understand why dictionary learning works analytically. In particular, if the observed data are generated from a ground truth dictionary, under what conditions can dictionary learning recovers the true dictionary? In the second part of the thesis, we studied the local correctness, or {\em local identifiability}, of a particular dictionary learning formulation with the $l_1$-norm objective function. Suppose we observe $N$ data points $\x_i\in \mathbb R^K$ for $i=1,...,N$, where $\x_i$'s are $i.i.d.$ random linear combinations of the $K$ columns from a square and invertible dictionary $\D_0 \in \mathbb R^{K\times K}$. We assumed that the random linear coefficients are generated from either the $s$-sparse Gaussian model or the Bernoulli-Gaussian model. For the population case, we established a sufficient and almost necessary condition for $\D_0$ to be locally identifiable, i.e., a local minimum of the expected $l_1$-norm objective function. Our condition covers both sparse and dense cases of the random linear coefficients and significantly improves the sufficient condition in Gribonval and Schnass (2010). Moreover, we demonstrated that for a complete $\mu$-coherent reference dictionary, i.e., a dictionary with absolute pairwise column inner-product at most $\coh\in[0,1)$, local identifiability holds even when the random linear coefficient vector has up to $O(\mu^{-2})$ nonzeros on average. Finally, it was shown that our local identifiability results translate to the finite sample case with high probability provided $N = O(K\log K)$.