2016/12/20 by Stojnic, Mihailo
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Control (math.OC) #Probability (math.PR)
paper · doi:10.48550/arxiv.1612.06839
Our companion work \citeStojnicl1BnBxasymldp considers random under-determined linear systems with box-constrained sparse solutions and provides an asymptotic analysis of a couple of modified ℓ1 heuristics adjusted to handle such systems (we refer to these modifications of the standard ℓ1 as binary and box ℓ1). Our earlier work \citeStojnicISIT2010binary established that the binary ℓ1 does exhibit the so-called phase-transition phenomenon (basically the same phenomenon well-known through earlier considerations to be a key feature of the standard ℓ1, see, e.g. \citeDonohoPol,DonohoUnsigned,StojnicCSetam09,StojnicUpper10). Moreover, in \citeStojnicISIT2010binary, we determined the precise location of the co-called phase-transition (PT) curve. On the other hand, in \citeStojnicl1BnBxasymldp we provide a much deeper understanding of the PTs and do so through a large deviations principles (LDP) type of analysis. In this paper we complement the results of \citeStojnicl1BnBxasymldp by leaving the asymptotic regime naturally assumed in the PT and LDP considerations aside and instead working in a finite dimensional setting. Along the same lines, we provide for both, the binary and the box ℓ1, precise finite dimensional analyses and essentially determine their ultimate statistical performance characterizations. On top of that, we explain how the results created here can be utilized in the asymptotic setting, considered in \citeStojnicl1BnBxasymldp, as well. Finally, for the completeness, we also present a collection of results obtained through numerical simulations and observe that they are in a massive agreement with our theoretical calculations.