Typical model reduction methods for parametric partial differential equations construct a linear space
V nwhich approximates well the solution manifold Mconsisting of all solutions u( y) with ythe vector of parameters. In many problems of numerical computation, nonlinear methods such as adaptive approximation, n-term approximation, and certain tree-based methods may provide improved numerical efficiency over linear methods. Nonlinear model reduction methods replace the linear space V nby a nonlinear space n. Little is known in terms of their performance guarantees, and most existing numerical experiments use a parameter dimension of at most two. In this work, we make a step towards a more cohesive theory for nonlinear model reduction. Framing these methods in the general setting of library approximation, we give a first comparison of their performance with the performance of standard linear approximation for any compact set. We then study these methods for solution manifolds of parametrized elliptic PDEs. We study a specific example of library approximation where the parameter domain is split into a finite number Nof rectangular cells, with affine spaces of dimension massigned to each cell, and give performance guarantees with respect to accuracy of approximation versus mand N.