  We introduce SPRING, a novel stochastic proximal alternating linearized
minimization algorithm for solving a class of non-smooth and non-convex
optimization problems. Large-scale imaging problems are becoming increasingly
prevalent due to advances in data acquisition and computational capabilities.
Motivated by the success of stochastic optimization methods, we propose a
stochastic variant of proximal alternating linearized minimization (PALM)
algorithm \cite{bolte2014proximal}. We provide global convergence guarantees,
demonstrating that our proposed method with variance-reduced stochastic
gradient estimators, such as SAGA \cite{SAGA} and SARAH \cite{sarah}, achieves
state-of-the-art oracle complexities. We also demonstrate the efficacy of our
algorithm via several numerical examples including sparse non-negative matrix
factorization, sparse principal component analysis, and blind image
deconvolution.
