Search

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]

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]

Abstract: In this paper, we study the performance of the projected Landweber iteration (PLW) for the general low rank matrix recovery. The PLW was first proposed by Zhang and Chen (2010) [43] based on the sparse recovery algorithm APG (Daubechies et al., 2008) [14] in the matrix completion setting, and numerical experiments have been given to show its efficiency (Zhang and Chen, 2010) [43]. In this paper, we focus on providing a convergence rate analysis of the PLW in the general setting of low rank matrix recovery with the affine transform having the matrix restricted isometry property. We show robustness of the algorithm to noise with a strong geometric convergence rate even for noisy measurements provided that the affine transform satisfies a matrix restricted isometry property condition. [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: 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]

Abstract: In this paper, we give a lower bound guaranteeing exact matrix completion via singular value thresholding (SVT) algorithm. The analysis shows that when the parameter in SVT algorithm is beyond some finite scalar, one can recover some unknown low-rank matrices exactly with high probability by solving a strictly convex optimization problem. Furthermore, we give an explicit expression for such a finite scalar. This result in the paper not only has theoretical interests, but also guides us to choose suitable parameters in the SVT algorithm. [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]

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]

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: 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: 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: 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: We introduce a randomized procedure that, given an matrix A and a positive integer k, approximates A with a matrix Z of rank k. The algorithm relies on applying a structured random matrix to each column of A, where l is an integer near to, but greater than, k. The structure of allows us to apply it to an arbitrary vector at a cost proportional to ; the resulting procedure can construct a rank-k approximation Z from the entries of A at a cost proportional to . We prove several bounds on the accuracy of the algorithm; one such bound guarantees that the spectral norm of the discrepancy between A and Z is of the same order as times the greatest singular value of A, with small probability of large deviations. In contrast, the classical pivoted “QR” decomposition algorithms (such as Gram–Schmidt or Householder) require at least kmn floating-point operations in order to compute a similarly accurate rank-k approximation. In practice, the algorithm of this paper runs faster than the classical algorithms, even when k is quite small or large. Furthermore, the algorithm operates reliably independently of the structure of the matrix A, can access each column of A independently and at most twice, and parallelizes naturally. Thus, the algorithm provides an efficient, reliable means for computing several of the greatest singular values and corresponding singular vectors of A. The results are illustrated via several numerical examples. [Copyright &y& Elsevier]

Abstract: In this paper we introduce an algorithm for the construction of interpolating scaling vectors on with compact support and orthonormal integer translates. Our method is substantiated by constructing several examples of bivariate scaling vectors for quincunx and box–spline dilation matrices. As the main ingredients of our recipe we derive some implementable conditions for accuracy and orthonormality of an interpolating scaling vector in terms of its mask. [Copyright &y& Elsevier]