ABSTRACT: This paper provides a framework for developing computationally efficient multilevel preconditioners and representations for Sobolev norms. Specifically, given a Hilbert space $V$ and a nested sequence of subspaces, $V_1 \subset V_2 \subset \ldots \subset V$, we construct operators which are spectrally equivalent to those of the form $\cA= \sum_k \mu_k (Q_k-Q_{k-1})$. Here $\mu_k$, $k=1,2,\ldots$ are positive numbers and $Q_k$ is the orthogonal projector onto $V_k$ with $Q_0=0$. We first present abstract results which show when $\cA$ is spectrally equivalent to a similarly constructed operator $\widetilde \cA$ defined in terms of an approximation $\widetilde Q_k$ of $Q_k$ , for $k=1,2, \ldots$ . We show that these results lead to efficient preconditioners for discretizations of differential and pseudo-differential operators of positive and negative order. These results extend to sums of operators. For example, singularly perturbed problems such as $I-\epsilon \Delta$ can be preconditioned uniformly independently of the parameter $\epsilon$. We also show how to precondition an operator which results from Tikhonov regularization of a problem with noisy data. Finally, we describe how the technique provides computationally efficient bounded discrete extensions which have applications to domain decomposition.