Search

It was recently shown that on a large class of important Banach spaces there exist no linear methods which are able to approximate the Hilbert transform from samples of the given function. This implies that there is no linear algorithm for calculating the Hilbert transform which can be implemented on a digital computer and which converges for all functions from the corresponding Banach spaces. The present paper develops a much more general framework which also includes non-linear approximation methods. All algorithms within this framework have only to satisfy an axiom which guarantees the computability of the algorithm based on given samples of the function. The paper investigates whether there exists an algorithm within this general framework which converges to the Hilbert transform for all functions in these Banach spaces. It is shown that non-linear methods give actually no improvement over linear methods. Moreover, the paper discusses some consequences regarding the Turing computability of the Hilbert transform and the existence of computational bases in Banach spaces. [ABSTRACT FROM AUTHOR]

Our goal in the paper is to address the following problem: From an unknown matrix, we are given inner products of that matrix with a set of prescribed matrices, and wish to find the unknown matrix. We shall consider this problem by using the notion of minimal norm interpolation. A fixed-point proximity algorithm for solving this problem will be developed. [ABSTRACT FROM AUTHOR]

In this paper, we study regression problems over a separable Hilbert space with the square loss, covering non-parametric regression over a reproducing kernel Hilbert space. We investigate a class of spectral/regularized algorithms, including ridge regression, principal component regression, and gradient methods. We prove optimal, high-probability convergence results in terms of variants of norms for the studied algorithms, considering a capacity assumption on the hypothesis space and a general source condition on the target function. Consequently, we obtain almost sure convergence results with optimal rates. Our results improve and generalize previous results, filling a theoretical gap for the non-attainable cases. [ABSTRACT FROM AUTHOR]

One important problem in the theory of Hardy space is to find the best rational approximation of a given order to a function in the Hardy space H 2 on the unit disk. It is equivalent to finding the best Blaschke form with free poles. The cyclic adaptive Fourier decomposition method is based on the grid search technique. Its approximative precision is limited by the grid spacing. This paper proposes two enhanced methods of the cyclic adaptive Fourier decomposition. The proposed algorithms utilize the gradient descent optimization to tune the best pole-tuple on the mesh grids, reaching higher precision. Their performances are confirmed by several examples. [ABSTRACT FROM AUTHOR]

We introduce in this paper fixed-point proximity-gradient algorithms for solving a class of structured convex optimization problems arising from image restoration. The objective function of such optimization problems is the sum of three convex functions. We study in this paper the scenario where one of the convex functions involved is differentiable with a Lipschitz continuous gradient and another convex function is composed by an affine transformation. We first characterize the solutions of the optimization problem as fixed-points of a mapping defined in terms of the gradient of the differentiable function and the proximity operators of the other two functions. Then, a fixed-point proximity-gradient iterative scheme is developed based on the fixed-point equation which characterizes the solutions. We establish the convergence of the proposed iterative scheme by the notion of averaged nonexpansive operators. Moreover, we obtain that in general the proposed iterative scheme has O ( 1 k ) convergence rate in the ergodic sense and the sense of partial primal–dual gap. Under stronger assumptions on the convex functions involved the proposed iterative scheme will converge linearly. We in particular derive fixed-point proximity-gradient algorithms from the proposed iterative scheme. The quasi-Newton and the overrelaxation strategies are designed to accelerate the algorithms. Numerical experiments for the computerized tomography reconstruction problem demonstrate that the proposed algorithms perform favorably and the quasi-Newton as well as the overrelaxation strategies significantly accelerate the convergence of the algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new multiscale representation of surfaces using tight wavelet frames. Both triangular and quadrilateral (quad) surfaces are considered. The multiscale representation for triangulated surfaces is generalized from the non-tensor-product tight wavelet frame representation of functions (of two variables) that were introduced in [1] , while the tensor-product tight frames of continuous linear B-spline from [63] are used for quad surfaces representation. As one of many possible applications of such representation, we consider surface denoising as an example at the end of the paper. We propose an analysis based surface denoising model for triangular and quad surfaces. Fast numerical algorithms are also proposed, which is different from the algorithms used in image restoration [50,52] due to the nonlinear nature of the proposed tight wavelet frame transforms on surfaces. [ABSTRACT FROM AUTHOR]

In this paper, we develop a novel and effective Euclidean algorithm for Laurent polynomial matrix extension (LPME), which is the key of the construction of perfect reconstruction filter banks (PRFBs). The algorithm gives an approach to the construction of PRFBs other than the dual-chain approach in the paper [5] . The developed algorithm can also be used in the applications where LPME plays a role. [ABSTRACT FROM AUTHOR]

The main objective of this paper is to find algorithms accompanied by explicit error bounds for phase retrieval from noisy magnitudes of frame coefficients when the underlying frame has a low redundancy. We achieve these goals with frames consisting of N = 6 d − 3 vectors spanning a d -dimensional complex Hilbert space. The two algorithms we use, phase propagation or the kernel method, are polynomial time in the dimension d . To ensure a successful approximate recovery, we assume that the noise is sufficiently small compared to the squared norm of the vector to be recovered. In this regime, we derive an explicit error bound that is inverse proportional to the signal-to-noise ratio, with a constant of proportionality that depends only on the dimension d . Properties of the reproducing kernel space of complex polynomials and of trigonometric polynomials are central in our error estimates. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we continue our investigation of symmetric tight framelet filter banks (STFFBs) with a minimum number of generators in [6]. In particular, we shall systematically study STFFBs with three high-pass filters which are derived from the oblique extension principle. To our best knowledge, except the papers [1,10], there are no other papers in the literature so far systematically studying this problem. In this paper we show that there are two different types, called type I and type II, of STFFBs with three high-pass filters. Then we provide a detailed analysis and a complete algorithm to obtain all type I STFFBs with three high-pass filters. Our results not only significantly generalize the results in [1,10], but also help us answer several unresolved problems on STFFBs. Based on [6], we also propose an algorithm to construct all type II STFFBs with three high-pass filters and with the shortest possible filter supports. Several examples are given to illustrate the results and algorithms in this paper. [Copyright &y& Elsevier]

Abstract: As demonstrated by Slepian et al. in a sequence of classical papers (see Slepian (1983) [33], Slepian and Pollak (1961) [34], Landau and Pollak (1961) [18], Slepian and Pollak (1964) [35], Slepian (1965) [36]), prolate spheroidal wave functions (PSWFs) provide a natural and efficient tool for computing with bandlimited functions defined on an interval. Recently, PSWFs have been becoming increasingly popular in various areas in which such functions occur – this includes physics (e.g. wave phenomena, fluid dynamics), engineering (signal processing, filter design), etc. To use PSWFs as a computational tool, one needs fast and accurate numerical algorithms for the evaluation of PSWFs and related quantities, as well as for the construction of corresponding quadrature rules, interpolation formulas, etc. During the last 15 years, substantial progress has been made in the design of such algorithms – see, for example, Xiao et al. (2001) [40] (see also Bowkamp (1947) [6], Slepian and Pollak (1961) [34], Landau and Pollak (1961) [18], Slepian and Pollak (1964) [35] for some classical results). The complexity of many of the existing algorithms, however, is at least quadratic in the band limit c. For example, the evaluation of the nth eigenvalue of the prolate integral operator requires operations (see e.g. Xiao et al. (2001) [40]); the construction of accurate quadrature rules for the integration (and associated interpolation) of bandlimited functions with band limit c requires operations (see e.g. Cheng et al. (1999) [8]). Therefore, while the existing algorithms are satisfactory for moderate values of c (e.g. ), they tend to be relatively slow when c is large (e.g. ). In this paper, we describe several numerical algorithms for the evaluation of PSWFs and related quantities, and design a class of PSWF-based quadratures for the integration of bandlimited functions. While the analysis is somewhat involved and will be published separately (currently, it can be found in Osipov and Rokhlin (2012) [27]), the resulting numerical algorithms are quite simple and efficient in practice. For example, the evaluation of the nth eigenvalue of the prolate integral operator requires operations; the construction of accurate quadrature rules for the integration (and associated interpolation) of bandlimited functions with band limit c requires operations. All algorithms described in this paper produce results essentially to machine precision. Our results are illustrated via several numerical experiments. [Copyright &y& Elsevier]

Abstract: The oblique extension principle introduced in Chui et al. (2002), Daubechies et al. (2003) [3,5] is a general procedure to construct tight wavelet frames and their associated filter banks. Symmetric tight framelet filter banks with two high-pass filters have been studied in Han and Mo (2004), Mo and Zhuang (in press), Petukhov (2003) [13,16,17]. Tight framelet filter banks with or without symmetry have been constructed in many papers in the literature. This paper is largely motivated by several results in Han (2010), Han and Mo (2004), Petukhov (2003) [11,13,17] to further study tight wavelet frames and their associated filter banks with symmetry and two high-pass filters. Our study not only leads to a simpler algorithm for the construction of tight framelet filter banks with symmetry and two high-pass filters, but also allows us to obtain a wider class of tight wavelet frames with symmetry which are not available in the current literature. The key ingredient in our investigation is a complete characterization of splitting positive semi-definite matrices of Laurent polynomials with symmetry. Several examples are provided to illustrate the results and algorithms in this paper. [Copyright &y& Elsevier]

Abstract: A dual-chain approach is introduced in this paper to construct dual wavelet filter systems with an arbitrary integer dilation . Starting from a pair of -dual low-pass filters, with , a top–down chain of filters is constructed with consecutive -dual pairs , , and , where and for all , and denotes the number of filter taps of . This enables the formulation of the filter system , with , to be used as the second component of the initial filter system of the bottom–up -dual chain: , constructed bottom–up iteratively, from to , by using both the -duality property of , and the unimodular property of the polyphase Laurent polynomial matrix associated with the filter system . Then the desired dual wavelet filter systems, associated with a and , are given by and . More importantly, the constructive algorithm for this dual-chain approach can be appropriately modified to preserve the symmetry property of the initial -dual pair . For any dilation factor , the dual-chain algorithms developed in this paper provide two systematic methods for the construction of both biorthogonal wavelets and bottom–up wavelets with or without the symmetry property. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate the biorthogonal matrix extension problem with symmetry and its application to construction of biorthogonal multiwavelets. Given a pair of biorthogonal matrices , the biorthogonal matrix extension problem is to find a pair of extension matrices of Laurent polynomials with symmetry such that the submatrix of the first r rows of is the given matrix , respectively; and are biorthogonal satisfying ; and and have the same compatible symmetry. We satisfactorily solve the biorthogonal matrix extension problem with symmetry and provide a step-by-step algorithm for constructing the desired pair of extension matrices from the given pair of matrices . Moreover, our results cover the case for paraunitary matrix extension with symmetry (i.e., the given pair satisfies ). Matrix extension plays an important role in many areas such as wavelet analysis, electronic engineering, system sciences, and so on. As an application of our general results on biorthogonal matrix extension with symmetry, we obtain a satisfactory algorithm for constructing univariate biorthogonal multiwavelets with symmetry for any dilation factor from a given pair of biorthogonal -refinable function vectors with symmetry. Correspondingly, pairs of -dual filter banks with the perfect reconstruction property and with symmetry can be derived by applying our algorithm to a given pair of -dual low-pass filters with symmetry. Several examples of symmetric biorthogonal multiwavelets are provided to illustrate our results in this paper. [Copyright &y& Elsevier]

Time–frequency analysis for non-linear and non-stationary signals is extraordinarily challenging. To capture features in these signals, it is necessary for the analysis methods to be local, adaptive and stable. In recent years, decomposition based analysis methods, such as the empirical mode decomposition (EMD) technique pioneered by Huang et al., were developed by different research groups. These methods decompose a signal into a finite number of components on which the time–frequency analysis can be applied more effectively. In this paper we consider the Iterative Filtering (IF) approach as an alternative to EMD. We provide sufficient conditions on the filters that ensure the convergence of IF applied to any L 2 signal. Then we propose a new technique, the Adaptive Local Iterative Filtering (ALIF) method, which uses the IF strategy together with an adaptive and data driven filter length selection to achieve the decomposition. Furthermore we design smooth filters with compact support from solutions of Fokker–Planck equations (FP filters) that can be used within both IF and ALIF methods. These filters fulfill the derived sufficient conditions for the convergence of the IF algorithm. Numerical examples are given to demonstrate the performance and stability of IF and ALIF techniques with FP filters. In addition, in order to have a complete and truly local analysis toolbox for non-linear and non-stationary signals, we propose new definitions for the instantaneous frequency and phase which depend exclusively on local properties of a signal. [ABSTRACT FROM AUTHOR]

Abstract: Image inpainting has been widely used in practice to repair damaged/missing pixels of given images. Most of the existing inpainting techniques require knowing beforehand where those damaged pixels are, either given as a priori or detected by some pre-processing. However, in certain applications, such information neither is available nor can be reliably pre-detected, e.g. removing random-valued impulse noise from images or removing certain scratches from archived photographs. This paper introduces a blind inpainting model to solve this type of problems, i.e., a model of simultaneously identifying and recovering damaged pixels of the given image. A tight frame based regularization approach is developed in this paper for such blind inpainting problems, and the resulted minimization problem is solved by the split Bregman algorithm first proposed by Goldstein and Osher (2009) . The proposed blind inpainting method is applied to various challenging image restoration tasks, including recovering images that are blurry and damaged by scratches and removing image noise mixed with both Gaussian and random-valued impulse noise. The experiments show that our method is compared favorably against many available two-staged methods in these applications. [Copyright &y& Elsevier]

Abstract: In this paper, we will present a generalization for a minimization problem from I. Daubechies, M. Defrise, and C. DeMol (2004) . This generalization is useful for solving many practical problems in which more than one constraint are involved. In this regard, we will conclude the findings of many papers (most of which are on image processing) from this generalization. It is hoped that the approach proposed in this paper will be a suitable reference for some applied works where multi-frames, multi-wavelets, or multi-constraints are present in linear inverse problems. [Copyright &y& Elsevier]

Abstract: In this paper we investigate the construction of dyadic affine (wavelet) bi-frames for triangular-mesh surface multiresolution processing. We introduce 6-fold symmetric bi-frames with 4 framelets (frame generators). 6-fold symmetric bi-frames yield frame decomposition and reconstruction algorithms (for regular vertices) with high symmetry, which is required for the design of the corresponding frame multiresolution algorithms for extraordinary vertices on the triangular mesh. Compared with biorthogonal wavelets, the constructed bi-frames have better smoothness and smaller supports. In addition, we also provide frame multiresolution algorithms for extraordinary vertices. All the frame algorithms considered in this paper are given by templates (stencils) so that they are implementable. Furthermore, we present some preliminary experimental results on surface processing with frame algorithms constructed in this paper. [Copyright &y& Elsevier]

Abstract: Recovering missing data from its partial samples is a fundamental problem in mathematics and it has wide range of applications in image and signal processing. While many such algorithms have been developed recently, there are very few papers available on their error estimations. This paper is to analyze the error of a frame based data recovery approach from random samples. In particular, we estimate the error between the underlying original data and the approximate solution that interpolates (or approximates with an error bound depending on the noise level) the given data that has the minimal norm of the canonical frame coefficients among all the possible solutions. [Copyright &y& Elsevier]

Abstract: Given an matrix A and a positive integer k, we describe a randomized procedure for the approximation of A with a matrix Z of rank k. The procedure relies on applying to a collection of l random vectors, where l is an integer equal to or slightly greater than k; the scheme is efficient whenever A and can be applied rapidly to arbitrary vectors. The discrepancy between A and Z is of the same order as times the st greatest singular value of A, with negligible probability of even moderately large deviations. The actual estimates derived in the paper are fairly complicated, but are simpler when is a fixed small nonnegative integer. For example, according to one of our estimates for , the probability that the spectral norm is greater than is less than . The paper contains a number of estimates for , including several that are stronger (but more detailed) than the preceding example; some of the estimates are effectively independent of m. Thus, given a matrix A of limited numerical rank, such that both A and can be applied rapidly to arbitrary vectors, the scheme provides a simple, efficient means for constructing an accurate approximation to a singular value decomposition of A. Furthermore, the algorithm presented here operates reliably independently of the structure of the matrix A. The results are illustrated via several numerical examples. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we investigate the minimax properties of Stein block thresholding in any dimension d with a particular emphasis on . Towards this goal, we consider a frame coefficient space over which minimaxity is proved. The choice of this space is inspired by the characterization provided in [L. Borup, M. Nielsen, Frame decomposition of decomposition spaces, J. Fourier Anal. Appl. 13 (1) (2007) 39–70] of family of smoothness spaces on , a subclass of so-called decomposition spaces [H.G. Feichtinger, Banach spaces of distributions defined by decomposition methods, II, Math. Nachr. 132 (1987) 207–237]. These smoothness spaces cover the classical case of Besov spaces, as well as smoothness spaces corresponding to curvelet-type constructions. Our main theoretical result investigates the minimax rates over these decomposition spaces, and shows that our block estimator can achieve the optimal minimax rate, or is at least nearly-minimax (up to a log factor) in the least favorable situation. Another contribution is that the minimax rates given here are stated for a noise sequence model in the transform coefficient domain satisfying some mild assumptions. This covers for instance the Gaussian case with frames where the noise is not white in the coefficient domain. The choice of the threshold parameter is theoretically discussed and its optimal value is stated for some noise models such as the (non-necessarily i.i.d.) Gaussian case. We provide a simple, fast and a practical procedure. We also report a comprehensive simulation study to support our theoretical findings. The practical performance of our Stein block denoising compares very favorably to the BLS-GSM state-of-the art denoising algorithm on a large set of test images. A toolbox is made available for download on the Internet to reproduce the results discussed in this paper. [Copyright &y& Elsevier]

Abstract: Compressed sensing is a technique to sample compressible signals below the Nyquist rate, whilst still allowing near optimal reconstruction of the signal. In this paper we present a theoretical analysis of the iterative hard thresholding algorithm when applied to the compressed sensing recovery problem. We show that the algorithm has the following properties (made more precise in the main text of the paper) [•] It gives near-optimal error guarantees. [•] It is robust to observation noise. [•] It succeeds with a minimum number of observations. [•] It can be used with any sampling operator for which the operator and its adjoint can be computed. [•] The memory requirement is linear in the problem size. [•] Its computational complexity per iteration is of the same order as the application of the measurement operator or its adjoint. [•] It requires a fixed number of iterations depending only on the logarithm of a form of signal to noise ratio of the signal. [•] Its performance guarantees are uniform in that they only depend on properties of the sampling operator and signal sparsity. [Copyright &y& Elsevier]

Abstract: Compactly supported Riesz wavelets are of interest in several applications such as image processing, computer graphics and numerical algorithms. In this paper, we shall investigate compactly supported MRA Riesz multiwavelet bases in . An algorithm is presented to derive Riesz multiwavelet bases from refinable function vectors. To illustrate our algorithm and results in this paper, we present several examples of Riesz multiwavelet bases with short support in . [Copyright &y& Elsevier]

Integer DCTs have important applications in lossless coding. In this paper, an integer DCT of radix-2 length n is understood to be a nonlinear, (left-)invertible mapping which acts on Zn and approximates the classical discrete cosine transform (DCT) of length n. In image compression, the DCT of type II (DCT-II) is of special interest. In this paper we present a new approach to invertible integer DCT-II and integer DCT-IV. Our method is based on a factorization of the cosine matrices of types II and IV into products of sparse, orthogonal matrices. Up to some permutations, each matrix factor is a block-diagonal matrix with blocks being orthogonal matrices of order 2. Hence one has to construct only integer transforms of length 2. We factorize an orthogonal matrix of order 2 into three lifting matrices and work with lifting steps and rounding-off. This allows the construction of new integer DCT algorithms. We give uniform bounds for the worst case difference between the results of exact DCT and the corresponding integer DCT. Finally, we present some numerical experiments for the integer DCT-II of length 8 and for the 2-dimensional integer DCT-II of size 8×8. [Copyright &y& Elsevier]

Can compression algorithms be employed for recovering signals from their underdetermined set of linear measurements? Addressing this question is the first step towards applying compression algorithms for compressed sensing (CS). In this paper, we consider a family of compression algorithms C r , parametrized by rate r , for a compact class of signals Q ⊂ R n . The set of natural images and JPEG at different rates are examples of Q and C r , respectively. We establish a connection between the rate–distortion performance of C r , and the number of linear measurements required for successful recovery in CS. We then propose compressible signal pursuit (CSP) algorithm and prove that, with high probability, it accurately and robustly recovers signals from an underdetermined set of linear measurements. We also explore the performance of CSP in the recovery of infinite dimensional signals. [ABSTRACT FROM AUTHOR]

Since its appearing in 1996, the Stockwell transform (S-transform) has been applied to medical imaging, geophysics and signal processing in general. In this paper, we prove that the system of functions (so-called DOST basis) is indeed an orthonormal basis of L 2 ( [ 0 , 1 ] ) , which is time–frequency localized, in the sense of Donoho–Stark Theorem (1989) [11] . Our approach provides a unified setting in which to study the Stockwell transform (associated with different admissible windows) and its orthogonal decomposition. Finally, we introduce a fast – O ( N log ⁡ N ) – algorithm to compute the Stockwell coefficients for an admissible window. Our algorithm extends the one proposed by Y. Wang and J. Orchard (2009) [33] . [ABSTRACT FROM AUTHOR]

Matrix completion involves recovering a matrix from a subset of its entries by utilizing interdependency between the entries, typically through low rank structure. Despite matrix completion requiring the global solution of a non-convex objective, there are many computationally efficient algorithms which are effective for a broad class of matrices. In this paper, we introduce an alternating steepest descent algorithm (ASD) and a scaled variant, ScaledASD, for the fixed-rank matrix completion problem. Empirical evaluation of ASD and ScaledASD on both image inpainting and random problems show they are competitive with other state-of-the-art matrix completion algorithms in terms of recoverable rank and overall computational time. In particular, their low per iteration computational complexity makes ASD and ScaledASD efficient for large size problems, especially when computing the solutions to moderate accuracy such as in the presence of model misfit, noise, and/or as an initialization strategy for higher order methods. A preliminary convergence analysis is also presented. [ABSTRACT FROM AUTHOR]

This paper is concerned with the question of reconstructing a vector in a finite-dimensional real Hilbert space when only the magnitudes of the coefficients of the vector under a redundant linear map are known. We analyze various Lipschitz bounds of the nonlinear analysis map and we establish theoretical performance bounds of any reconstruction algorithm. The discussion of robustness is with respect to random noise and with respect to deterministic perturbations. We show that robust and uniformly stable reconstruction is not achievable with the minimum redundancy for phaseless reconstruction. Robust reconstruction schemes require additional redundancy than the critical threshold. [ABSTRACT FROM AUTHOR]

In Compressive Sensing, the Restricted Isometry Property (RIP) ensures that robust recovery of sparse vectors is possible from noisy, undersampled measurements via computationally tractable algorithms. It is by now well-known that Gaussian (or, more generally, sub-Gaussian) random matrices satisfy the RIP under certain conditions on the number of measurements. Their use can be limited in practice, however, due to storage limitations, computational considerations, or the mismatch of such matrices with certain measurement architectures. These issues have recently motivated considerable effort towards studying the RIP for structured random matrices. In this paper, we study the RIP for block diagonal measurement matrices where each block on the main diagonal is itself a sub-Gaussian random matrix. Our main result states that such matrices can indeed satisfy the RIP but that the requisite number of measurements depends on certain properties of the basis in which the signals are sparse. In the best case, these matrices perform nearly as well as dense Gaussian random matrices, despite having many fewer nonzero entries. [ABSTRACT FROM AUTHOR]

Block coherence of matrices plays an important role in analyzing the performance of block compressed sensing recovery algorithms (Bajwa and Mixon, 2012). In this paper, we characterize two block coherence metrics: worst-case and average block coherence. First, we present lower bounds on worst-case block coherence, in both the general case and also when the matrix is constrained to be a union of orthobases. We then present deterministic matrix constructions based upon Kronecker products which obtain these lower bounds. We also characterize the worst-case block coherence of random subspaces. Finally, we present a flipping algorithm that can improve the average block coherence of a matrix, while maintaining the worst-case block coherence of the original matrix. We provide numerical examples which demonstrate that our proposed deterministic matrix construction performs well in block compressed sensing. [ABSTRACT FROM AUTHOR]

Abstract: This article considers recovery of signals that are sparse or approximately sparse in terms of a (possibly) highly overcomplete and coherent tight frame from undersampled data corrupted with additive noise. We show that the properly constrained -analysis optimization problem, called analysis Dantzig selector, stably recovers a signal which is nearly sparse in terms of a tight frame provided that the measurement matrix satisfies a restricted isometry property adapted to the tight frame. As a special case, we consider the Gaussian noise. Further, under a sparsity scenario, with high probability, the recovery error from noisy data is within a log-like factor of the minimax risk over the class of vectors which are at most s sparse in terms of the tight frame. Similar results for the analysis LASSO are shown. The above two algorithms provide guarantees only for noise that is bounded or bounded with high probability (for example, Gaussian noise). However, when the underlying measurements are corrupted by sparse noise, these algorithms perform suboptimally. We propose new algorithms for reconstructing signals that are nearly sparse in terms of a tight frame in the presence of bounded noise combined with sparse noise, and present corresponding recovery guarantees. The analysis in this paper is based on the restricted isometry property adapted to a tight frame, which is a natural extension to the standard restricted isometry property. [Copyright &y& Elsevier]

Abstract: Optimizing the acquisition matrix is useful for compressed sensing of signals that are sparse in overcomplete dictionaries, because the acquisition matrix can be adapted to the particular correlations of the dictionary atoms. In this paper a novel formulation of the optimization problem is proposed, in the form of a rank-constrained nearest correlation matrix problem. Furthermore, improvements for three existing optimization algorithms are introduced, which are shown to be particular instances of the proposed formulation. Simulation results show notable improvements and superior robustness in sparse signal recovery. [Copyright &y& Elsevier]

Abstract: It has recently been proved that the popular nonlocal means (NLM) denoising algorithm does not optimally denoise images with sharp edges. Its weakness lies in the isotropic nature of the neighborhoods it uses to set its smoothing weights. In response, in this paper we introduce several theoretical and practical anisotropic nonlocal means (ANLM) algorithms and prove that they are near minimax optimal for edge-dominated images from the Horizon class. On real-world test images, an ANLM algorithm that adapts to the underlying image gradients outperforms NLM by a significant margin. [Copyright &y& Elsevier]

Abstract: In this paper we propose a variation of the soft-thresholding algorithm for finding sparse approximate solutions of the equation , where as the sparsity of the iterate increases the penalty function changes. In this approach, sufficiently large entries in a sparse iterate are left untouched. The advantage of this approach is that a higher regularization constant can be used, leading to a significant reduction of the total number of iterations. Numerical experiments for sparse recovery problems, also with noisy data, are included. [Copyright &y& Elsevier]

Abstract: The local histogram transform of an image is a data cube that consists of the histograms of the pixel values that lie within a fixed neighborhood of any given pixel location. Such transforms are useful in image processing applications such as classification and segmentation, especially when dealing with textures that can be distinguished by the distributions of their pixel intensities and colors. We, in particular, use them to identify and delineate biological tissues found in histology images obtained via digital microscopy. In this paper, we introduce a mathematical formalism that rigorously justifies the use of local histograms for such purposes. We begin by discussing how local histograms can be computed as systems of convolutions. We then introduce probabilistic image models that can emulate textures one routinely encounters in histology images. These models are rooted in the concept of image occlusion. A simple model may, for example, generate textures by randomly speckling opaque blobs of one color on top of blobs of another. Under certain conditions, we show that, on average, the local histograms of such model-generated-textures are convex combinations of more basic distributions. We further provide several methods for creating models that meet these conditions; the textures generated by some of these models resemble those found in histology images. Taken together, these results suggest that histology textures can be analyzed by decomposing their local histograms into more basic components. We conclude with a proof-of-concept segmentation-and-classification algorithm based on these ideas, supported by numerical experimentation. [Copyright &y& Elsevier]

Abstract: In this paper we study the performance of the Projected Gradient Descent (PGD) algorithm for -constrained least squares problems that arise in the framework of compressed sensing. Relying on the restricted isometry property, we provide convergence guarantees for this algorithm for the entire range of , that include and generalize the existing results for the iterative hard thresholding algorithm and provide a new accuracy guarantee for the iterative soft thresholding algorithm as special cases. Our results suggest that in this group of algorithms, as p increases from zero to one, conditions required to guarantee accuracy become stricter and robustness to noise deteriorates. [Copyright &y& Elsevier]

Abstract: In this paper modified variants of the sparse Fourier transform algorithms from Iwen (2010) [32] are presented which improve on the approximation error bounds of the original algorithms. In addition, simple methods for extending the improved sparse Fourier transforms to higher dimensional settings are developed. As a consequence, approximate Fourier transforms are obtained which will identify a near-optimal k-term Fourier series for any given input function, , in time (neglecting logarithmic factors). Faster randomized Fourier algorithm variants with runtime complexities that scale linearly in the sparsity parameter k are also presented. [Copyright &y& Elsevier]

Abstract: After a decade of extensive study of the sparse representation synthesis model, we can safely say that this is a mature and stable field, with clear theoretical foundations, and appealing applications. Alongside this approach, there is an analysis counterpart model, which, despite its similarity to the synthesis alternative, is markedly different. Surprisingly, the analysis model did not get a similar attention, and its understanding today is shallow and partial. In this paper we take a closer look at the analysis approach, better define it as a generative model for signals, and contrast it with the synthesis one. This work proposes effective pursuit methods that aim to solve inverse problems regularized with the analysis-model prior, accompanied by a preliminary theoretical study of their performance. We demonstrate the effectiveness of the analysis model in several experiments, and provide a detailed study of the model associated with the 2D finite difference analysis operator, a close cousin of the TV norm. [Copyright &y& Elsevier]

Abstract: This paper investigates two parameters that measure the coherence of a frame: worst-case and average coherence. We first use worst-case and average coherence to derive near-optimal probabilistic guarantees on both sparse signal detection and reconstruction in the presence of noise. Next, we provide a catalog of nearly tight frames with small worst-case and average coherence. Later, we find a new lower bound on worst-case coherence; we compare it to the Welch bound and use it to interpret recently reported signal reconstruction results. Finally, we give an algorithm that transforms frames in a way that decreases average coherence without changing the spectral norm or worst-case coherence. [Copyright &y& Elsevier]

Abstract: Data sets are often modeled as samples from a probability distribution in , for D large. It is often assumed that the data has some interesting low-dimensional structure, for example that of a d-dimensional manifold , with d much smaller than D. When is simply a linear subspace, one may exploit this assumption for encoding efficiently the data by projecting onto a dictionary of d vectors in (for example found by SVD), at a cost for n data points. When is nonlinear, there are no “explicit” and algorithmically efficient constructions of dictionaries that achieve a similar efficiency: typically one uses either random dictionaries, or dictionaries obtained by black-box global optimization. In this paper we construct data-dependent multi-scale dictionaries that aim at efficiently encoding and manipulating the data. Their construction is fast, and so are the algorithms that map data points to dictionary coefficients and vice versa, in contrast with -type sparsity-seeking algorithms, but like adaptive nonlinear approximation in classical multi-scale analysis. In addition, data points are guaranteed to have a compressible representation in terms of the dictionary, depending on the assumptions on the geometry of the underlying probability distribution. [Copyright &y& Elsevier]

Abstract: A finite -frame variety consists of real or complex matrices satisfying and for all . This paper introduces an approximate geometric gradient descent procedure over these varieties, which is powered by minimization algorithms for the frame operator distance and recent characterizations of these varietiesʼ tangent spaces. For almost all compatible pairings , we demonstrate that minimization of the frame operator distance converges linearly under a threshold, we derive a process for constructing the orthogonal projection onto these varietiesʼ tangent spaces, and finally demonstrate that the approximate gradient descent procedure converges. Finally, we apply this procedure to numerically construct Grassmannian frames and Welch bound equality sequences with low mutual coherence. [Copyright &y& Elsevier]

Abstract: We introduce a method to re-parameterize massive high dimensional data, generated by nonlinear mixing, into its independent physical parameters. Our method enables the identification of the original parameters and their extension to new observations without any knowledge of the true physical model. The suggested approach in this paper is related to spectral independent components analysis (ICA) via the construction of an anisotropic diffusion kernel whose eigenfunctions comprise the independent components. However, we use a novel anisotropic diffusion process, utilizing only a small observed subset , that approximates the isotropic diffusion on the parametric manifold of the full set Y. We employ a Nyström-type extension of the independent components of to the independent components of Y, and provide a validation scheme for our algorithm parameters choice. We demonstrate our method on synthetic examples and on real application examples. [Copyright &y& Elsevier]

Abstract: In the theory of compressed sensing, restricted isometry analysis has become a standard tool for studying how efficiently a measurement matrix acquires information about sparse and compressible signals. Many recovery algorithms are known to succeed when the restricted isometry constants of the sampling matrix are small. Many potential applications of compressed sensing involve a data-acquisition process that proceeds by convolution with a random pulse followed by (nonrandom) subsampling. At present, the theoretical analysis of this measurement technique is lacking. This paper demonstrates that the sth-order restricted isometry constant is small when the number m of samples satisfies , where n is the length of the pulse. This bound improves on previous estimates, which exhibit quadratic scaling. [Copyright &y& Elsevier]

Abstract: Finite unit norm tight frames provide Parseval-like decompositions of vectors in terms of redundant components of equal weight. They are known to be robust against additive noise and erasures, and as such, have great potential as encoding schemes. Unfortunately, up to this point, these frames have proven notoriously difficult to construct. Indeed, though the set of all unit norm tight frames, modulo rotations, is known to contain manifolds of nontrivial dimension, we have but a small finite number of known constructions of such frames. In this paper, we present a new iterative algorithm—gradient descent of the frame potential—for increasing the degree of tightness of any finite unit norm frame. The algorithm itself is easy to implement, and it preserves certain group structures present in the initial frame. In the special case where the number of frame elements is relatively prime to the dimension of the underlying space, we show that this algorithm converges to a unit norm tight frame at a linear rate, provided the initial unit norm frame is already sufficiently close to being tight. By slightly modifying this approach, we get a similar, but weaker, result in the non-relatively-prime case, providing an explicit answer to the Paulsen problem: “How close is a frame which is almost tight and almost unit norm to some unit norm tight frame?” [Copyright &y& Elsevier]

Abstract: In this paper we present a necessary and sufficient condition to construct a symmetric framelet system , and having rational coefficients. Once a low-pass filter is given and such a necessary and sufficient condition is satisfied, a step-by-step algorithm will be used to construct a symmetric framelet filter bank with two high-pass filters and which is of interest in applications such as signal de-noising and image de-blurring, etc. Two new examples will be given to illustrate our results and the algorithm. [Copyright &y& Elsevier]

Abstract: We consider the regression problem by learning with a regularization scheme in a data dependent hypothesis space and -regularizer. The data dependence nature of the kernel-based hypothesis space provides flexibility for the learning algorithm. The regularization scheme is essentially different from the standard one in a reproducing kernel Hilbert space: the kernel is not necessarily symmetric or positive semi-definite and the regularizer is the -norm of a function expansion involving samples. The differences lead to additional difficulty in the error analysis. In this paper we apply concentration techniques with -empirical covering numbers to improve the learning rates for the algorithm. Sparsity of the algorithm is studied based on our error analysis. We also show that a function space involved in the error analysis induced by the -regularizer and non-symmetric kernel has nice behaviors in terms of the -empirical covering numbers of its unit ball. [Copyright &y& Elsevier]

Abstract: A recurring task in image processing, approximation theory, and the numerical solution of partial differential equations is to reconstruct a piecewise-smooth real-valued function , where , from its truncated Fourier transform (its truncated spectrum). An essential step is edge detection for which a variety of one-dimensional schemes have been developed over the last few decades. Most higher-dimensional edge detection algorithms consist of applying one-dimensional detectors in each component direction in order to recover the locations in where is singular (the singular support). In this paper, we present a multidimensional algorithm which identifies the wavefront of a function from spectral data. The wavefront of f is the set of points which encode both the location of the singular points of a function and the orientation of the singularities. (Here denotes the unit sphere in N dimensions.) More precisely, is the direction of the normal line to the curve or surface of discontinuity at x. Note that the singular support is simply the projection of the wavefront onto its x-component. In one dimension, the wavefront is a subset of , and it coincides with the singular support. In higher dimensions, geometry comes into play and they are distinct. We discuss the advantages of wavefront reconstruction and indicate how it can be used for segmentation in magnetic resonance imaging (MRI). [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we provide a mathematical foundation for the least square regression learning with indefinite kernel and coefficient regularization. Except for continuity and boundedness, the kernel function is not necessary to satisfy any further regularity conditions. An explicit expression of the solution via sampling operator and empirical integral operator is derived and plays an important role in our analysis. It provides a natural error decomposition where the approximation error is characterized by a reproducing kernel Hilbert space associated to certain Mercer kernel. A careful analysis shows the sample error has decay. We deduce the error bound and prove the asymptotic convergence. Satisfactory learning rates are then derived under a very mild regularity condition on the regression function. When the kernel is itself a Mercer kernel better rates are given by a rigorous analysis which shows coefficient regularization is powerful in learning smooth functions. The saturation effect and the relation to the spectral algorithms are discussed. [ABSTRACT FROM AUTHOR]

Abstract: Let with be a given nonnegative mask. Assume that the subdivision scheme with this mask is convergent. Let the associated refinable function be ϕ. So the support of ϕ is contained in . Melkman conjectured in 1997 that unless the scheme is interpolatory and the refinable function ϕ is positive on . In the present paper we confirm this conjecture. A lower bound of ϕ on is also given. [Copyright &y& Elsevier]

Abstract: Compressive sampling offers a new paradigm for acquiring signals that are compressible with respect to an orthonormal basis. The major algorithmic challenge in compressive sampling is to approximate a compressible signal from noisy samples. This paper describes a new iterative recovery algorithm called CoSaMP that delivers the same guarantees as the best optimization-based approaches. Moreover, this algorithm offers rigorous bounds on computational cost and storage. It is likely to be extremely efficient for practical problems because it requires only matrix–vector multiplies with the sampling matrix. For compressible signals, the running time is just , where N is the length of the signal. [Copyright &y& Elsevier]

Abstract: Anisotropic wavelet packets present a flexible transform with interesting properties and applications. While certain aspects of this transform have been investigated in conjunction with applications, this paper aims at providing a basic theoretical framework for working with anisotropic wavelet packets. Random decompositions are developed which have distributions with different average decomposition depths and degrees of anisotropy. They can be used in cryptographic applications or to test other algorithms. For the uniform distribution, it is necessary to determine the number of possible bases for all decomposition depths. A best basis algorithm for anisotropic decompositions is developed. A graph theoretical representation of the anisotropic decomposition structure is presented, which is unique for each decomposition and, thus, free of redundancy, which is important for compression purposes. A compression algorithm based on these techniques is developed and tested on random decompositions. [Copyright &y& Elsevier]