Is it true that all known sparse coding algorithms which work efficiently in practice don't have convergence proofs and always use an intermediate step of a matching/subspace pursuit algorithm on the current dictionary? And that this step of using a pursuit algorithm intermediate to solve a compressed sensing problem on the intermediate dictionaries is what is the hard part which is analytically intractable? Or is there any hardness result known for either matching pursuit algorithms or sparse coding? I understand that there are sparse coding algorithms with proofs like, arXiv:1206.5882 (full rank dictionary), arXiv:1309.1952, arXiv:1310.7991, arXiv:1503.00778, arXiv:1407.1543 but I would like to understand why these aren't the ones that is probably ever used in practice. It would be helpful if you could kindly add in other references that you might know of for either provable sparse coding or matching pursuit algorithms. 
Sparse coding and matching pursuit algorithms
cc.complexity theory;ds.algorithms;np hardness;approximation algorithms;sparse matrix