Sparse bilinear inverse problems arise in numerous applications including medical imaging, blind deconvolution, and dictionary learning. Recasting these inverse problems as compressed sensing of sparse rank-one matrices, we propose a computationally efficient alternating minimization algorithm called sparse power factorization (SPF). Starting from a particular initialization, SPF achieves guaranteed stable recovery with number of measurements within a logarithmic factor of the information-theoretic fundamental limit. Numerical results show that SPF empirically outperforms the best known combinations of mixed norm and nuclear norm.