We present an innovative approach to the synthesis of linear arrays having the least possible number of elements while radiating shaped beams lying in completely arbitrary power masks. The approach, based on theory and procedures lend from Compressive Sensing, has two innovative key features. First, it exploits at best the multiplicity of equivalent field solutions corresponding to the many different power patterns lying in the given mask. Second, it a-priori optimizes those parameters that affect the performance of Compressive Sensing. The overall problem is formulated as two convex programming routines plus one local optimization, with the inherent advantages in terms of computational time and solutions optimality. An extensive numerical comparison against state-of-the-art procedures proves the effectiveness of the approach.