We propose a new approach to construct adaptive multiscale orthonormal (AMO) bases of R^N that provide highly sparse signal representations. Our new multilayer AMO basis design produces a high proportion of small scale vectors. The basis vectors are built from small scale to large scales, layer by layer. For each layer, the basis vector maximizes a p-norm measure of sparsity. We compare the sparsity ratios SR, (i.e., the percentage of negligibly small coefficients) obtained with AMO and Daubechies wavelet bases for seven families of piecewise smooth signals with randomly located discontinuities. The signals are composed of polynomials, sinusoids and exponentials pieces. In all cases, AMO bases produce a SR increase ranging from 6% to 37%. AMO bases have three main advantages over wavelets. First, they are found automatically by solving a sequence of optimization problems, which eliminates the problem of selecting a wavelet for a given signal. Second, they can provide a significantly sparser representation. Finally, they have the ability to produce zero coefficients for a larger family of piecewise smooth signals. The drawbacks of AMO bases are computational: the basis computation is more expensive, the basis vectors require storage space and no fast transform is known.