Convergence analysis of tight framelet approach for missing data recovery

How to recover missing data from an incomplete samples is a fundamental problem in mathematics and it has wide range of applications in image analysis and processing. Although many existing methods, e.g. various data smoothing methods and PDE approaches, are available in the literature, there is always a need to find new methods leading to the best solution according to various cost functionals. In this paper, we propose an iterative algorithm based on tight framelets for image recovery from incomplete observed data. The algorithm is motivated from our framelet algorithm used in high-resolution image reconstruction and it exploits the redundance in tight framelet systems. We prove the convergence of the algorithm and also give its convergence factor. Furthermore, we derive the minimization properties of the algorithm and explore the roles of the redundancy of tight framelet systems. As an illustration of the effectiveness of the algorithm, we give an application of it in impulse noise removal.     

On Approximation with Spline Generated Framelets

We characterize the approximation spaces associated with the best n-term approximation in L_p(R) by elements from a tight wavelet frame associated with a spline scaling function. The approximation spaces are shown to be interpolation spaces between L_p and classical Besov spaces, and the result coincides with the result for nonlinear approximation with an orthonormal wavelet with the same smoothness as the spline scaling function. We also show that, under certain conditions, the Besov smoothness can be measured in terms of the sparsity of expansions in the wavelet frame, just like the nonredundant wavelet case. However, the characterization now holds even for wavelet frame systems that do not have the usually required number of vanishing moments, e.g., for systems built through the Unitary Extension Principle, which can have no more than one vanishing moment. Using these results, we describe a fast algorithm that takes as input any function and provides a near sparsest expansion of it in the framelet system as well as approximants that reach the optimal rate of nonlinear approximation. Together with the existence of a fast algorithm, the absence of the need for vanishing moments may have an important qualitative impact for applications to signal compression, as high vanishing moments usually introduce a Gibbs-type phenomenon (or ringing artifacts)in the approximants.     

Tensor train rank minimization with hybrid smoothness regularization for visual data recovery

Recently, the tensor train (TT) rank has received much attention for tensor completion, due to its ability to explore the global low-rankness of tensors. However, existing methods still leave room for improvement, since the low-rankness itself is generally not sufficient to recover the underlying data. Inspired by this, we consider a novel tensor completion model by simultaneously exploiting the global low-rankness and local smoothness of visual data. In particular, we use low-rank matrix factorization to characterize the global TT low-rankness, and framelet and total variation regularization to enhance the local smoothness. We develop an efficient proximal alternating minimization algorithm to solve the proposed new model with guaranteed convergence. Extensive experiments on various data demonstrated that the proposed method outperforms compared methods in terms of visual and quantitative measures.     

Symmetric orthogonal approximation to symmetric tensors with applications to image reconstruction

The main objective of this paper is to study an approximation of symmetric tensors by symmetric orthogonal decomposition. We propose and study an iterative algorithm to determine a symmetric orthogonal approximation and analyze the convergence of the proposed algorithm. Numerical examples are reported to demonstrate the effectiveness of the proposed algorithm. We also apply the proposed algorithm to represent correlated face images. We demonstrate better face image reconstruction results by combining principal components and symmetric orthogonal approximation instead of combining principal components and higher‐order SVD results.     

On the existence of multiresolution analysis for framelets

We show that a compactly supported tight framelet comes from an MRA if the intersection of all dyadic dilations of the space of negative dilates, which is defined as the shift-invariant space generated by the negative scales of a framelet, is trivial. We also construct examples of (non-tight) framelets, which are arbitrarily close to tight frame framelets, such that the corresponding space of negative dilates is equal to the entire space L ²ℝ.The first author was partially supported by the NSF grant DMS–0441817     

Construction of Multivariate Tight Framelet Packets Associated with Dilation Matrix

In this paper, we present a method for constructing multivariate tight framelet packets associated with an arbitrary dilation matrix using unitary extension principles.We also prove how to construct various tight frames for L2(Rd) by replac-ing some mother framelets.     

An approximation algorithm for scheduling trees of malleable tasks

This work presents an approximation algorithm for scheduling the tasks of a parallel application. These tasks are considered as malleable tasks (MT in short), which means that they can be executed on several processors. This model receives recently a lot of attention, mainly due to their practical use for implementing actual parallel applications. Most of the works developed within this model deal with independent MT for which good approximation algorithms have been designed. This work is devoted to the case where MT are linked by precedence relations. We present a 4(1+ϵ) approximation algorithm (for any fixed ϵ) for the specific structure of a tree. This preliminary result should open the way for further investigations concerning arbitrary precedence graphs of MT.     

Approximation by matrices with restricted spectra

We investigate the properties of the approximation of a matrix by matrices whose spectra are in a closed convex set of the complex plane. We explain why the Khalil and Maher characterization of an approximant, which spectrum is in a strip, is not quite correct. We prove that their characterization is valid but for another kind of approximation. We formulate a conjecture which leads to some algorithm for computing approximants. The conjecture is motivated by numerical experiments and some theoretical considerations. Separately we consider the approximation of normal matrices.     

Approximation algorithms for the m-dimensional 0–1 knapsack problem: Worst-case and probabilistic analyses

We describe a polynomial approximation scheme for an m-constraint 0–1 integer programming problem (m fixed) based on the use of the dual simplex algorithm for linear programming.We also analyse the asymptotic properties of a particular random model.     

Free gradient discontinuity and image inpainting

We introduce and study a formulation of the inpainting problem for two-dimensional images that are locally damaged. This formulation is based on the regularization of the solution of a second-order variational problem with Dirichlet boundary condition. A variational approximation algorithm is proposed. Bibliography: 45 titles.     

Modeling and analysis of power-tail distributions via classical teletraffic methods

We propose a new methodology for modeling and analyzing power-tail distributions, such as the Pareto distribution, in communication networks. The basis of our approach is a fitting algorithm which approximates a power-tail distribution by a hyperexponential distribution. This algorithm possesses several key properties. First, the approximation can be achieved within any desired degree of accuracy. Second, the fitted hyperexponential distribution depends only on a few parameters. Third, only a small number of exponentials are required in order to obtain an accurate approximation over many time scales. Once equipped with a fitted hyperexponential distribution, we have an integrated framework for analyzing queueing systems with power-tail distributions. We consider the GI/G/1 queue with Pareto distributed service time and show how our approach allows to derive both quantitative numerical results and asymptotic closed-form results. This derivation shows that classical teletraffic methods can be employed for the analysis of power-tail distributions. This revised version was published online in June 2006 with corrections to the Cover Date.     

The application of an oblique-projected Landweber method to a model of supervised learning

This paper brings together a novel information representation model for use in signal processing and computer vision problems, with a particular algorithmic development of the Landweber iterative algorithm. The information representation model allows a representation of multiple values for a variable as well as an expression for confidence. Both properties are important for effective computation using multi-level models, where a choice between models will be implementable as part of the optimization process. It is shown that in this way the algorithm can deal with a class of high-dimensional, sparse, and constrained least-squares problems, which arise in various computer vision learning tasks, such as object recognition and object pose estimation. While the algorithm has been applied to the solution of such problems, it has so far been used heuristically. In this paper we describe the properties and some of the peculiarities of the channel representation and optimization, and put them on firm mathematical ground. We consider the optimization a convexly constrained weighted least-squares problem and propose for its solution a projected Landweber method which employs oblique projections onto the closed convex constraint set. We formulate the problem, present the algorithm and work out its convergence properties, including a rate-of-convergence result. The results are put in perspective with currently available projected Landweber methods. An application to supervised learning is described, and the method is evaluated in an experiment involving function approximation, as well as application to transient signals.     

Variational Bayes and the Reduced Dependence Approximation for the Autologistic Model on an Irregular Grid With Applications

Discrete Markov random field models provide a natural framework for representing images or spatial datasets. They model the spatial association present while providing a convenient Markovian dependency structure and strong edge-preservation properties. However, parameter estimation for discrete Markov random field models is difficult due to the complex form of the associated normalizing constant for the likelihood function. For large lattices, the reduced dependence approximation to the normalizing constant is based on the concept of performing computationally efficient and feasible forward recursions on smaller sublattices, which are then suitably combined to estimate the constant for the entire lattice. We present an efficient computational extension of the forward recursion approach for the autologistic model to lattices that have an irregularly shaped boundary and that may contain regions with no data; these lattices are typical in applications. Consequently, we also extend the reduced dependence approximation to these scenarios, enabling us to implement a practical and efficient nonsimulation-based approach for spatial data analysis within the variational Bayesian framework. The methodology is illustrated through application to simulated data and example images. The online supplementary materials include our C++ source code for computing the approximate normalizing constant and simulation studies.     

A Multinomial Approximation Approach for the Finite Time Survival Probability Under the Markov-modulated Risk Model

In this paper, we consider the problem of computing different types of finite time survival probabilities for a Markov-Modulated risk model and a Markov-Modulated risk model with reinsurance, both with varying premium rates. We use the multinomial approximation scheme to derive an efficient recursive algorithm to compute finite time survival probabilities and finite time draw-down survival probabilities. Numerical results show that by comparing with MCMC approximation, discretize approximation and diffusion approximation methods, the proposed scheme performs accurate results in all the considered cases and with better computation efficiency.

     

On the use of piecewise linear models in nonlinear programming

This paper presents an active-set algorithm for large-scale optimization that occupies the middle ground between sequential quadratic programming and sequential linear-quadratic programming methods. It consists of two phases. The algorithm first minimizes a piecewise linear approximation of the Lagrangian, subject to a linearization of the constraints, to determine a working set. Then, an equality constrained subproblem based on this working set and using second derivative information is solved in order to promote fast convergence. A study of the local and global convergence properties of the algorithm highlights the importance of the placement of the interpolation points that determine the piecewise linear model of the Lagrangian.     

A class of tight framelet packets

This paper obtains a class of tight framelet packets on L ²(ℝ ^d ) from the extension principles and constructs the relationships between the basic framelet packets and the associated filters.     

A multiresolution analysis for tensor-product splines using weighted spline wavelets

We construct biorthogonal spline wavelets for periodic splines which extend the notion of “lazy” wavelets for linear functions (where the wavelets are simply a subset of the scaling functions) to splines of higher degree. We then use the lifting scheme in order to improve the approximation properties with respect to a norm induced by a weighted inner product with a piecewise constant weight function. Using the lifted wavelets we define a multiresolution analysis of tensor-product spline functions and apply it to image compression of black-and-white images. By performing-as a model problem-image compression with black-and-white images, we demonstrate that the use of a weight function allows to adapt the norm to the specific problem.     

Stopping rules for a nonnegatively constrained iterative method for ill-posed Poisson imaging problems

Image data is often collected by a charge coupled device (CCD) camera. CCD camera noise is known to be well-modeled by a Poisson distribution. If this is taken into account, the negative-log of the Poisson likelihood is the resulting data-fidelity function. We derive, via a Taylor series argument, a weighted least squares approximation of the negative-log of the Poisson likelihood function. The image deblurring algorithm of interest is then applied to the problem of minimizing this weighted least squares function subject to a nonnegativity constraint. Our objective in this paper is the development of stopping rules for this algorithm. We present three stopping rules and then test them on data generated using two different true images and an accurate CCD camera noise model. The results indicate that each of the three stopping rules is effective. AMS subject classification (2000)  65F20, 65F30     

Wavelet Foveation

A foveated image is a nonuniform resolution image whose resolution is highest at a point (fovea) but falls off away from the fovea. It can be obtained from a uniform image through a space-variant smoothing process, where the width of the smoothing function is small near the fovea and gradually expanding as the distance from the fovea increases. We treat this process as an integral operator and analyze its kernel. This kernel is dominated by its diagonal in the wavelet bases and thus permits a fast algorithm for foveating images. In addition, the transformed kernel takes a simple form which can be easily computed using a look-up table. This is useful, since in applications the fovea changes rapidly. We describe an application of our approximation algorithm in image visualization over the Internet.