Numerically erasure-robust frames

Given a channel with additive noise and adversarial erasures, the task is to design a frame that allows for stable signal reconstruction from transmitted frame coefficients. To meet these specifications, we introduce numerically erasure-robust frames. We first consider a variety of constructions, including random frames, equiangular tight frames and group frames. Later, we show that arbitrarily large erasure rates necessarily induce numerical instability in signal reconstruction. We conclude with a few observations, including some implications for maximal equiangular tight frames and sparse frames.     

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.     

Stable recovery of signals from frame coefficients with erasures at unknown locations

In an earlier work, we proposed a frame-based kernel analysis approach to the problem of recovering erasures from unknown locations. The new approach led to the stability question on recovering a signal from noisy partial frame coefficients with erasures occurring at unknown locations. In this continuing work, we settle this problem by obtaining a complete characterization of frames that provide stable reconstructions. We show that an encoding frame provides a stable signal recovery from noisy partial frame coefficients at unknown locations if and only if it is totally robust with respect to erasures. We present several characterizations for either totally robust frames or almost robust frames. Based on these characterizations several explicit construction algorithms for totally robust and almost robust frames are proposed. As a consequence of the construction methods, we obtain that the probability for a randomly generated frame to be totally robust with respect to a fixed number of erasures is one.     

Quantized Frame Expansions with Erasures

Frames have been used to capture significant signal characteristics, provide numerical stability of reconstruction, and enhance resilience to additive noise. This paper places frames in a new setting, where some of the elements are deleted. Since proper subsets of frames are sometimes themselves frames, a quantized frame expansion can be a useful representation even when some transform coefficients are lost in transmission. This yields robustness to losses in packet networks such as the Internet. With a simple model for quantization error, it is shown that a normalized frame minimizes mean-squared error if and only if it is tight. With one coefficient erased, a tight frame is again optimal among normalized frames, both in average and worst-case scenarios. For more erasures, a general analysis indicates some optimal designs. Being left with a tight frame after erasures minimizes distortion, but considering also the transmission rate and possible erasure events complicates optimizations greatly.     

Linearly connected sequences and spectrally optimal dual frames for erasures

In the case that a frame is prescribed for applications and erasures occur in the process of data transmissions, we examine optimal dual frames for the recovery from single erasures. In contrast to earlier papers, we consider the spectral radius of the error operator instead of its operator norm as a measure of optimality. This notion of optimality is natural when the Neumann series is used to recover the original data in an iterative manner. We obtain a complete characterization of spectrally one-erasure optimal dual frames in terms of the redundancy distribution of the prescribed frame. Our characterization relies on the connection between erasure optimal frames and the linear connectivity property of the frame. We prove that the linear connectivity property is equivalent to the intersection dependent property, and is also closely related to the well-known concept of a k-independent set. Additionally, we also establish several necessary and sufficient conditions for the existence of an alternate dual frame to make the iterative reconstruction work.     

Optimal dual frames for erasures

For any given frame (for the purpose of encoding) in a finite dimensional Hilbert space, we investigate its dual frames that are optimal for erasures (for the purpose of decoding). We show that in general the canonical dual is not necessarily optimal. Moreover, optimal dual frames are not necessarily unique. We present some sufficient conditions under which the canonical dual is the unique optimal dual frame for the erasure problem. As an application, we get that the canonical dual is the only optimal dual when either the frame is induced by a group representation or the frame is uniform tight.     

Random Matrices and Erasure Robust Frames

Data erasure can often occur in communication. Guarding against erasures involves redundancy in data representation. Mathematically this may be achieved by redundancy through the use of frames. One way to measure the robustness of a frame against erasures is to examine the worst case condition number of the frame with a certain number of vectors erased from the frame. The term numerically erasure-robust frames was introduced in Fickus and Mixon (Linear Algebra Appl 437:1394–1407, 2012) to give a more precise characterization of erasure robustness of frames. In the paper the authors established that random frames whose entries are drawn independently from the standard normal distribution can be robust against up to approximately 15 % erasures, and asked whether there exist frames that are robust against erasures of more than 50 %. In this paper we show that with very high probability random frames are, independent of the dimension, robust against erasures as long as the number of remaining vectors is at least \(1+\delta _0\) times the dimension for some \(\delta _0>0\). This is the best possible result, and it also implies that the proportion of erasures can be arbitrarily close to 1 while still maintaining robustness. Our result depends crucially on a new estimate for the smallest singular value of a rectangular random matrix with independent standard normal entries.     

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

Linearized decomposition codes and finite integer set coverings

In this paper, we study parallel erasure correction (PEC) matrix codes capable of correcting multiple row erasures simultaneously. Our PEC codes are based on linearized decomposition (LD) of polynomials and we show that the LD codes are capable of row erasure correction using small locality sets, even if roughly half the rows are erased. We also study coverings of finite set of integers using predetermined neighbourhoods and use the covering estimate obtained, to bound the rate of LD codes.     

等距丢失模型下的框架张量积重构方法

框架理论常应用于信号重构.当编码系数在传输过程中发生等距丢失时,基于框架张量积的一些性质,我们可以利用框架张量积对信号进行编码从而降低数据丢失对重构信号的影响.本文由此提出了一种等距丢失模型,并在此模型下,研究了数据等距丢失下的最优对偶框架张量积,得出了对偶框架和正则对偶框架的张量积是最优对偶框架张量积的两个充分必要条件.最后数值实验也说明了：在等距丢失模型下,最优对偶框架张量积比一般对偶框架张量积的信号重构结果更优.     

Equal-Norm Tight Frames with Erasures

Equal-norm tight frames have been shown to be useful for robust data transmission. The losses in the network are modeled as erasures of transmitted frame coefficients. We give the first systematic study of the general class of equal-norm tight frames and their properties. We search for efficient constructions of such frames. We show that the only equal-norm tight frames with the group structure and one or two generators are the generalized harmonic frames. Finally, we give a complete classification of frames in terms of their robustness to erasures.     

Failed disk recovery in double erasure RAID arrays

Reliability is a major concern in the design of large disk arrays. In this paper, we examine the effect of encountering more failures than that for which the RAID array was initially designed. Erasure codes are incorporated to enable system recovery from a specified number of disk erasures, and strive beyond that threshold to recover the system as frequently, and as thoroughly, as is possible. Erasure codes for tolerating two disk failures are examined. For these double erasure codes, we establish a correspondence between system operation and acyclicity of its graph model. For the most compact double erasure code, the full 2-code, this underlies an efficient algorithm for the computation of system operation probability (all disks operating or recoverable).When the system has failed, some disks are nonetheless recoverable. We extend the graph model to determine the probability that d disks have failed, a of which are recoverable by solving one linear equation, b of which are further recoverable by solving systems of linear equations, and d−a−b of which cannot be recovered. These statistics are efficiently calculated for the full 2-code by developing a three variable ordinary generating function whose coefficients give the specified values. Finally, examples are given to illustrate the probability that an individual disk can be recovered, even when the system is in a failed state.     

Erasure Decoding for Gabidulin Codes

We present a new approach of the decoding algorithm for Gabidulin Codes. In the same way as efficient erasure decoding for Generalized Reed Solomon codes by using the structure of the inverse of the VanderMonde matrices, we show that, the erasure(t erasures mean that t components of a code vector are erased) decoding Gabidulin code can be seen as a computation of three matrice and an affine permutation, instead of computing an inverse from the generator or parity check matrix. This significantly reduces the decoding complexity compared to others algorithms. For t erasures with t ≤ r, where r = n − k, the erasure algorithm decoding for Gab _{n, k} (g) Gabidulin code compute the t symbols by simple multiplication of three matrices. That requires rt + r(k − 1) Galois field multiplications, t(r − 1) + (t + r)k field additions, r ² + r(k + 1) field negations and t(k + 1) field inversions.     

Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization

This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-uniform and unknown sampling distributions. This method significantly relaxes the uniform sampling assumption imposed for the widely used nuclear-norm penalized approach, and makes low-rank matrix recovery feasible in more practical settings. Theoretically, we prove that the proposed estimator achieves fast rates of convergence under different settings. Computationally, we propose an alternating direction method of multipliers algorithm to efficiently compute the estimator, which bridges a gap between theory and practice of machine learning methods with max-norm regularization. Further, we provide thorough numerical studies to evaluate the proposed method using both simulated and real datasets.     

Hierarchical erasure correction of linear codes

Linear codes over finite extension fields have widespread applications in theory and practice. In some scenarios, the decoder has a sequential access to the codeword symbols, giving rise to a hierarchical erasure structure. In this paper we develop a mathematical framework for hierarchical erasures over extension fields, provide several bounds and constructions, and discuss potential applications in distributed storage and flash memories. Our results show intimate connection to Universally Decodable Matrices, as well as to Reed-Solomon and Gabidulin codes.     

Spatial approximation of stochastic convolutions

We study linear stochastic evolution partial differential equations driven by additive noise. We present a general and flexible framework for representing the infinite dimensional Wiener process, which drives the equation. Since the eigenfunctions and eigenvalues of the covariance operator of the process are usually not available for computations, we propose an expansion in an arbitrary frame. We show how to obtain error estimates when the truncated expansion is used in the equation. For the stochastic heat and wave equations, we combine the truncated expansion with a standard finite element method and derive a priori bounds for the mean square error. Specializing the frame to biorthogonal wavelets in one variable, we show how the hierarchical structure, support and cancelation properties of the primal and dual bases lead to near sparsity and can be used to simplify the simulation of the noise and its update when new terms are added to the expansion.     

Design of RLS Wiener fixed-lag smoother using covariance information in linear discrete stochastic systems

In this paper, we propose a new design for the recursive least-squares (RLS) Wiener fixed-lag smoother and filter in linear discrete-time wide-sense stationary stochastic systems. It is assumed that the signal is observed with additive white observation noise. The signal is uncorrelated with the observation noise. The estimators require knowledge of the system matrix, the observation matrix and the variance of the state vector. These quantities can be obtained from the auto-covariance function of the signal. In the estimation algorithms, moreover, the variance of the observation noise is assumed to be known, as a priori information.     

New characterizations of fusion frames (frames of subspaces)

In this article, we give new characterizations of fusion frames, on the properties of their synthesis operators, on the behavior of fusion frames under bounded operators with closed range, and on erasures of subspaces of fusion frames. Furthermore we show that every fusion frame is the image of an orthonormal fusion basis under a bounded surjective operator.     

Full Spark Frames

Finite frame theory has a number of real-world applications. In applications like sparse signal processing, data transmission with robustness to erasures, and reconstruction without phase, there is a pressing need for deterministic constructions of frames with the following property: every size-M subcollection of the M-dimensional frame elements is a spanning set. Such frames are called full spark frames, and this paper provides new constructions using the discrete Fourier transform. Later, we prove that full spark Parseval frames are dense in the entire set of Parseval frames, meaning full spark frames are abundant, even if one imposes an additional tightness constraint. Finally, we prove that testing whether a given matrix is full spark is hard for NP under randomized polynomial-time reductions, indicating that deterministic full spark constructions are particularly significant because they guarantee a property which is otherwise difficult to check.     

Recovery of signals from unordered partial frame coefficients

In this paper, we study the feasibility and stability of recovering signals in finite-dimensional spaces from unordered partial frame coefficients. We prove that with an almost self-located robust frame, any signal except from a Lebesgue measure zero subset can be recovered from its unordered partial frame coefficients. However, the recovery is not necessarily stable with almost self-located robust frames. We propose a new class of frames, namely self-located robust frames, that ensures stable recovery for any input signal with unordered partial frame coefficients. In particular, the recovery is exact whenever the received unordered partial frame coefficients are noise-free. We also present some characterizations and constructions for (almost) self-located robust frames. Based on these characterizations and construction algorithms, we prove that any randomly generated frame is almost surely self-located robust. Moreover, frames generated with cube roots of different prime numbers are also self-located robust.