Reconstruction of Signals From Frame Coefficients With Erasures at Unknown Locations

We propose new approaches to the problems of recovering signals from the rearranged frame coefficients or frame coefficients with erasures at either known or unknown locations. These problems naturally arise from applications, where the encoded information needs to be transmitted, for example, in signal/image processing, information and coding theory, and communications. We show that with the appropriate choices of the frames that are used for encoding, the signal with erasures occurring at known locations can be easily recovered without inverting the (sub)frame operators each time. Our new easy to implement and cost-efficient algorithm provides perfect reconstruction of the original signal. To address the problem of recovering erased coefficients from unknown locations, we propose to use a class of frames that are almost robust with respect to m-erasures. We prove that every frame with uniform excess can be rescaled to an almost robust frame and the locations of erased data can be perfectly recovered for almost all the signals. Similar results are obtained for recovering the original order of a disordered (rearranged) set of frame coefficients. Numerical examples are presented to test the main results. Whenever the received data are noise free, we can recover the original signal exactly from frame coefficients with erasures at unknown locations or from a disordered set of frame coefficients.