Coarse-to-fine manifold learning

R.M. Castro, R. Willett, R. Nowak

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


    In this paper we consider a sequential, coarse-to-fine estimation of a piecewise constant function with smooth boundaries. Accurate detection and localization of the boundary (a manifold) is the key aspect of this problem. In general, algorithms capable of achieving optimal performance require exhaustive searches over large dictionaries that grow exponentially with the dimension of the observation domain. The computational burden of the search hinders the use of such techniques in practice, and motivates our work. We consider a sequential, coarse-to-fine approach that involves first examining the data on a coarse grid, and then refining the analysis and approximation in regions of interest. Our estimators involve an almost linear-time (in two dimensions) sequential search over the dictionary, and converge at the same near-optimal rate as estimators based on exhaustive searches. Specifically, for two dimensions, our algorithm requires O(n76/) operations for an n-pixel image, much less than the traditional wedgelet approaches, which require O(n116/) operations.
    Original languageEnglish
    Title of host publicationProceedings IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP'04, Montreal, Canada, May 17-21, 2004)
    PublisherInstitute of Electrical and Electronics Engineers
    ISBN (Print)0-7803-8484-9
    Publication statusPublished - 2004


    Dive into the research topics of 'Coarse-to-fine manifold learning'. Together they form a unique fingerprint.

    Cite this