Random linear systems with sparse solutions -- finite dimensions

In our companion work citeStojnicl1RegPosasymldp we revisited random under-determined linear systems with sparse solutions. The main emphasis was on the performance analysis of the ℓ1 heuristic in the so-called asymptotic regime, i.e. in the regime where the systems' dimensions are large. Through an earlier sequence of work citeDonohoPol,DonohoUnsigned,StojnicCSetam09,StojnicUpper10, it is now well known that in such a regime the ℓ1 exhibits the so-called phase transition (PT) phenomenon. citeStojnicl1RegPosasymldp then went much further and established the so-called large deviations principle (LDP) type of behavior that characterizes not only the breaking points of the ℓ1's success but also the behavior in the entire so-called transition zone around these points. Both of these concepts, the PTs and the LDPs, are in fact defined so that one can use them to characterize the asymptotic behavior. In this paper we complement the results of citeStojnicl1RegPosasymldp by providing an exact detailed analysis in the non-asymptotic regime. Of course, not only are the non-asymptotic results complementing those from citeStojnicl1RegPosasymldp, they actually are the ones that ultimately fully characterize the ℓ1's behavior in the most general sense. We introduce several novel high-dimensional geometry type of strategies that enable us to eventually determine the ℓ1's behavior.