Robust dimension reduction,fusion frames,and Grassmannian packings

We consider estimating a random vector from its measurements in a fusion frame, in presence of noise and subspace erasures. A fusion frame is a collection of subspaces, for which the sum of the projection operators onto the subspaces is bounded below and above by constant multiples of the identity operator. We first consider the linear minimum mean-squared error (LMMSE) estimation of the random vector of interest from its fusion frame measurements in the presence of additive white noise. Each fusion frame measurement is a vector whose elements are inner products of an orthogonal basis for a fusion frame subspace and the random vector of interest. We derive bounds on the mean-squared error (MSE) and show that the MSE will achieve its lower bound if the fusion frame is tight. We then analyze the robustness of the constructed LMMSE estimator to erasures of the fusion frame subspaces. We limit our erasure analysis to the class of tight fusion frames and assume that all erasures are equally important. Under these assumptions, we prove that tight fusion frames consisting of equi-dimensional subspaces have maximum robustness (in the MSE sense) with respect to erasures of one subspace among all tight fusion frames, and that the optimal subspace dimension depends on signal-to-noise ratio (SNR). We also prove that tight fusion frames consisting of equi-dimensional subspaces with equal pairwise chordal distances are most robust with respect to two and more subspace erasures, among the class of equi-dimensional tight fusion frames. We call such fusion frames equi-distance tight fusion frames. We prove that the squared chordal distance between the subspaces in such fusion frames meets the so-called simplex bound, and thereby establish connections between equi-distance tight fusion frames and optimal Grassmannian packings. Finally, we present several examples for the construction of equi-distance tight fusion frames.     

On the construction of equiangular frames from graphs

We give details of the 1-1 correspondence between equiangular frames of n vectors for and graphs with n vertices. This has been studied recently for tight equiangular frames because of applications to signal processing and quantum information theory. The nontight examples given here (which correspond to graphs with more than 2 eigenvalues) have the potential for similar applications, e.g., the frame corresponding to the 5-cycle graph is the unique Grassmannian frame of 5 vectors in openR³. Further, the associated canonical tight frames have a small number of angles in many cases.     

Geometry of the Welch bounds

A geometric perspective involving Grammian and frame operators is used to derive the entire family of Welch bounds. This perspective unifies a number of observations that have been made regarding tightness of the bounds and their connections to symmetric k-tensors, tight frames, homogeneous polynomials, and t-designs. In particular, a connection has been drawn between sampling of homogeneous polynomials and frames of symmetric k-tensors. It is also shown that tightness of the bounds requires tight frames. The lack of tight frames of symmetric k-tensors in many cases, however, leads to consideration of sets that come as close as possible to attaining the bounds. The geometric derivation is then extended in the setting of generalized or continuous frames. The Welch bounds for finite sets and countably infinite sets become special cases of this general setting.     

Generation of finite tight frames by Householder transformations

Finite tight frames are widely used for many applications. An important problem is to construct finite frames with prescribed norm for each vector in the tight frame. In this paper we provide a fast and simple algorithm for such a purpose. Our algorithm employs the Householder transformations. For a finite tight frame consisting of m vectors in ?ⁿ or ?ⁿ only O(nm) operations are needed. In addition, we also study the following question: Given a set of vectors in ?ⁿ or ?ⁿ, how many additional vectors, possibly with constraints, does one need to add in order to obtain a tight frame?     

On the Duality Principle by Casazza, Kutyniok, and?Lammers

The R-dual sequences of a frame {f _i } _i∈I , introduced by Casazza, Kutyniok and Lammers in (J. Fourier Anal. Appl. 10(4):383–408, 2004), provide a powerful tool in the analysis of duality relations in general frame theory. In this paper we derive conditions for a sequence {ω _j } _j∈I to be an R-dual of a given frame {f _i } _i∈I . In particular we show that the R-duals {ω _j } _j∈I can be characterized in terms of frame properties of an associated sequence {n _i } _i∈I . We also derive the duality results obtained for tight Gabor frames in (Casazza et al. in J. Fourier Anal. Appl. 10(4):383–408, 2004) as a special case of a general statement for R-duals of frames in Hilbert spaces. Finally we consider a relaxation of the R-dual setup of independent interest. Several examples illustrate the results.     

Critical Pairs of Sequences of a Mixed Frame Potential

The classical frame potential in a finite-dimensional Hilbert space has been introduced by Benedetto and Fickus, who showed that all finite unit-norm tight frames can be characterized as the minimizers of this energy functional. This was the starting point of a series of new results in frame theory, related to finding tight frames with determined lengths. The frame potential has been studied in the traditional setting as well as in the finite-dimensional fusion frame context. In this work we introduce the concept of mixed frame potential, which generalizes the notion of the Benedetto-Fickus frame potential. We study properties of this new potential, and give the structure of its critical pairs of sequences on a suitable restricted domain. For a given sequence {α _m } _{m=1,…, N} in K, where K is ? or ?, we obtain necessary and sufficient conditions in order to have a dual pair of frames {f _m } _{m=1,…, N} , {g _m } _{m=1,…, N} such that ? f _m , g _m  ? = α _m for all m = 1,…, N.     

Random Tight Frames

We introduce probabilistic frames to study finite frames whose elements are chosen at random. While finite tight frames generalize orthonormal bases by allowing redundancy, independent, uniformly distributed points on the sphere approximately form a finite unit norm tight frame (FUNTF). In the present paper, we develop probabilistic versions of tight frames and FUNTFs to significantly weaken the requirements on the random choice of points to obtain an approximate finite tight frame. Namely, points can be chosen from any probabilistic tight frame, they do not have to be identically distributed, nor have unit norm. We also observe that classes of random matrices used in compressed sensing are induced by probabilistic tight frames.     

Auto-tuning unit norm frames

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?”     

Norm Retrievable Frames and Their Perturbation in Finite Dimensional Complex Hilbert Spaces

In this article, we study the property of norm retrievability of spanning vectors in a finite dimensional complex Hilbert space ?. Using the set of zero trace operators on ? and two sets of self-adjoint operators on ? denoted by 𝒮^1,0 and 𝒮^1,1, we present some equivalent conditions to the norm retrievable frames in ?. We will also show that the property of norm retrievability for n-dimensional complex Hilbert space ? with n≠2 is stable under enough small perturbation of the frame set only for phase retrievable frames.     

Minimizing Fusion Frame Potential

Fusion frames are an emerging topic of frame theory, with applications to encoding and distributed sensing. However, little is known about the existence of tight fusion frames. In traditional frame theory, one method for showing that unit norm tight frames exist is to characterize them as the minimizers of an energy functional, known as the frame potential. We generalize the frame potential to the fusion frame setting. In particular, we introduce the fusion frame potential, and show how its minimization is equivalent to the minimization of the traditional frame potential over a particular domain. We then study this minimization problem in detail. Specifically, we show that if the desired number of fusion frame subspaces is large, and if the desired dimension of these subspaces is small compared to the dimension of the underlying space, then a tight fusion frame of those dimensions will necessarily exist, being a minimizer of the fusion frame potential.     

Characterization and Computation of Canonical Tight Windows for Gabor Frames

Let (\gnm)_{n,m ? \Zst}(\gnm)_{n,m\in\Zst} be a Gabor frame for \LtR\LtR for given window gg. We show that the window \ho = \SQI g\ho=\SQI g that generates the canonically associated tight Gabor frame minimizes ||g-h||\|g-h\| among all windows hh generating a normalized tight Gabor frame. We present and prove versions of this result in the time domain, the frequency domain, the time-frequency domain, and the Zak transform domain, where in each domain the canonical \ho\ho is expressed using functional calculus for Gabor frame operators. Furthermore, we derive a Wiener--Levy type theorem for rationally oversampled Gabor frames. Finally, a Newton-type method for a fast numerical calculation of \ho\ho is presented. We analyze the convergence behavior of this method and demonstrate the efficiency of the proposed algorithm by some numerical examples.     

Iteratively reweighted algorithm for signals recovery with coherent tight frame

We consider the problem of compressed sensing with a coherent tight frame and design an iteratively reweighted least squares algorithm to solve it. To analyze the problem, we propose a sufficient null space property under a tight frame (sufficient D‐NSP). We show that, if a measurement matrix A satisfies the sufficient D‐NSP of order s, then an s‐sparse signal under the tight frame can be exactly recovered. Furthermore, if A satisfies the restricted isometric property with tight frame D of order 2bs, then it also satisfies the sufficient D‐NSP of order as with a < b and b sufficiently large. We prove the convergence of the algorithm based on the sufficient D‐NSP and give the upper error bounds. In numerical experiments, we use the discrete cosine transform, discrete Fourier transform, and Haar wavelets to verify the effectiveness of this algorithm. With increasing measurement number, the signal‐to‐noise ratio increases monotonically.     

On the Twistor Spaces of Almost Hermitian Manifolds

We study Grassmannian bundles G_k(M) of analytical 2k-planes over an almost Hermitian manifold M²ⁿ, from the point of view of the generalized twistor spaces of [13], and with the method of the moving frame [9]. G₁(M⁴) is the classical twistor space. We find four distinguished almost Hermitian structures, one of them being that of [13], and discuss their integrability and Kählerianity. For n=2, we compute the corresponding Hermitian connections, and derive consequences about the corresponding first Chern classes.     

Frames, modular functions for shift-invariant subspaces and FMRA wavelet frames

We introduce the concept of the modular function for a shift-invariant subspace that can be represented by normalized tight frame generators for the shift-invariant subspace and prove that it is independent of the selections of the frame generators for the subspace. We shall apply it to study the connections between the dimension functions of wavelet frames for any expansive integer matrix and the multiplicity functions for general multiresolution analysis (GMRA). Given a frame mutiresolution analysis (FMRA), we show that the standard construction formula for orthonormal multiresolution analysis wavelets does not yield wavelet frames unless the underlying FMRA is an MRA. A modified explicit construction formula for FMRA wavelet frames is given in terms of the frame scaling functions and the low-pass filters.

     

A coefficient inequality for Bloch functions with applications to uniformly locally univalent functions

We give a Fekete-Szeg? type inequality for an analytic function on the unit disk with Bloch seminorm ≤1. As an application of it, we derive a sharp inequality for the third coefficient of a uniformly locally univalent function f(z) = z + a ₂ z ² + a ₃ z ³ + ⋯ on the unit disk with pre-Schwarzian norm ≤λ for a given λ > 0.     

Sums of Hilbert space frames

We give simple necessary and sufficient conditions on Bessel sequences {fi} and {gi} and operators L₁, L₂ on a Hilbert space H so that {L₁fi+L₂gi} is a frame for H. This allows us to construct a large number of new Hilbert space frames from existing frames.     

Componentwise error analysis for FFTs with applications to fast Helmholtz solvers

We analyze the stability of the Cooley-Tukey algorithm for the Fast Fourier Transform of ordern=2 ^k and of its inverse by using componentwise error analysis.We prove that the components of the roundoff errors are linearly related to the result in exact arithmetic. We describe the structure of the error matrix and we give optimal bounds for the total error in infinity norm and inL ₂ norm.The theoretical upper bounds are based on a worst case analysis where all the rounding errors work in the same direction. We show by means of a statistical error analysis that in realistic cases the max-norm error grows asymptotically like the logarithm of the sequence length by machine precision.Finally, we use the previous results for introducing tight upper bounds on the algorithmic error for some of the classical fast Helmholtz equation solvers based on the Faster Fourier Transform and for some algorithms used in the study of turbulence.     

Expansion of frames to tight frames

We show that every Bessel sequence （and therefore every frame） in a separable Hilbert space can be expanded to a tight frame by adding some elements. The proof is based on a recent generalization of the frame concept, the g-frame, which illustrates that g-frames could be useful in the study of frame theory. As an application, we prove that any Gabor frame can be expanded to a tight frame by adding one window function.     

Parseval wavelets on hierarchical graphs

Wavelets on graphs have been studied for the past few years, and in particular, several approaches have been proposed to design wavelet transforms on hierarchical graphs. Although such methods are computationally efficient and easy to implement, their frames are highly restricted. In this paper, we propose a general framework for the design of wavelet transforms on hierarchical graphs. Our design is guaranteed to be a Parseval tight frame, which preserves the $l_2$ norm of any input signals. To demonstrate the potential usefulness of our approach, we perform several experiments, in which we learn a wavelet frame based on our framework, and show, in inpainting experiments, that it performs better than a Haar-like hierarchical wavelet transform and a learned treelet. We also show with category theory that the algebraic properties of the proposed transform have a strong relationship with those of the hierarchical graph that represents the structure of the given data.     

Polynomial approximation on the sphere using scattered data

We consider the problem of approximately reconstructing a function f defined on the surface of the unit sphere in the Euclidean space ℝ^{q +1} by using samples of f at scattered sites. A central role is played by the construction of a new operator for polynomial approximation, which is a uniformly bounded quasi‐projection in the de la Vallée Poussin style, i.e. it reproduces spherical polynomials up to a certain degree and has uniformly bounded L^p operator norm for 1 ≤ p ≤ ∞. Using certain positive quadrature rules for scattered sites due to Mhaskar, Narcowich and Ward, we discretize this operator obtaining a polynomial approximation of the target function which can be computed from scattered data and provides the same approximation degree of the best polynomial approximation. To establish the error estimates we use Marcinkiewicz–Zygmund inequalities, which we derive from our continuous approximating operator. We give concrete bounds for all constants in the Marcinkiewicz–Zygmund inequalities as well as in the error estimates. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)