2009 SCAIM Seminar - 08

We consider regular geometric subdivisions. These combine the refinement of a regular lattice with a regular pattern of affine transformations applied to geometric data associated with the nodes of the lattice. Such subdivisions are used in computer aided geometric design for surface modeling and in the film industry for scene and character design and animation. A multi-resolution combines subdivision-based approximation with efficient representation of the approximation error, and in this form has application to image compression. This talk will outline an approach to the constriction of a multi-resolution from a given subdivision. The construction is purely geometric and linear-algebraic in form and makes repeated use of the singular values decomposition. In brief, given the matrix of affine transformations, P, that maps the points c of a lattice to the points f of a refined lattice, the construction provides a reverse mapping Af = c that consists of an oblique projection founded on a geometric argument. If the points f are not the exact products of a subdivision; e.g. are measured data, Pc will not equal f, and the construction provides mappings B and Q such that d=Bf and Qd represents the error in Pc. Any matrix representing such a P will be regular and banded, and it is a requirement that the construction provide matrices representing A, B, and Q that are of similar character. In particular this requirement proceeds from the fact that, in a multi-resolution, the data c and d must occupy no more storage than the data f, which puts significant restrictions on the construction. Nevertheless, these restrictions provide the impetus for organizing the construction entirely in terms of the interaction between the short intervals of the nonzeros in the rows of one matrix with the columns of another matrix. The construction never has to deal with any matrix in its entirety.