Mean squared error bounds for the Rangan–Goyal soft thresholding algorithm

The Rangan–Goyal (RG) algorithm is an iterative method, based on soft thresholding, for constructing an estimate xN∈Rd of a signal x∈Rd, given N⩾d frame coefficients of x that have been corrupted by uniform noise. It has been proven by Rangan and Goyal that for every p<1, the RG-algorithm has reconstruction error that satisfies limN→∞‖x−xN‖Np=0 almost surely, where the randomization is taken over the choice of frame and the corrupting noise sequence. It is proven here that the RG-algorithm achieves mean squared error (MSE) of the optimal order E‖x−xN‖2⩽C/N2 in the setting of random frames. There are, however, concrete scenarios where the algorithm performs poorly for specific (deterministically chosen) frames. The issue of frame ordering plays an important role in the deterministic setting. It is shown here that for suitable orderings of deterministic frames the RG-algorithm has reconstruction error E‖x−xN‖2⩽C/N2, where the expectation only involves the corrupting noise sequence and where C is an explicit constant.