Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTARM: A Turbo-type Algorithm for Affine Rank Minimization
73
0
0.0
(
0
)
Added by
Zhipeng Xue
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The affine rank minimization (ARM) problem arises in many real-world applications. The goal is to recover a low-rank matrix from a small amount of noisy affine measurements. The original problem is NP-hard, and so directly solving the problem is computationally prohibitive. Approximate low-complexity solutions for ARM have recently attracted much research interest. In this paper, we design an iterative algorithm for ARM based on message passing principles. The proposed algorithm is termed turbo-type ARM (TARM), as inspired by the recently developed turbo compressed sensing algorithm for sparse signal recovery. We show that, when the linear operator for measurement is right-orthogonally invariant (ROIL), a scalar function called state evolution can be established to accurately predict the behaviour of the TARM algorithm. We also show that TARM converges much faster than the counterpart algorithms for low-rank matrix recovery. We further extend the TARM algorithm for matrix completion, where the measurement operator corresponds to a random selection matrix. We show that, although the state evolution is not accurate for matrix completion, the TARM algorithm with carefully tuned parameters still significantly outperforms its counterparts.
rate research
Read More
In this paper, the problem of matrix rank minimization under affine constraints is addressed. The state-of-the-art algorithms can recover matrices with a rank much less than what is sufficient for the uniqueness of the solution of this optimization problem. We propose an algorithm based on a smooth approximation of the rank function, which practically improves recovery limits on the rank of the solution. This approximation leads to a non-convex program; thus, to avoid getting trapped in local solutions, we use the following scheme. Initially, a rough approximation of the rank function subject to the affine constraints is optimized. As the algorithm proceeds, finer approximations of the rank are optimized and the solver is initialized with the solution of the previous approximation until reaching the desired accuracy. On the theoretical side, benefiting from the spherical section property, we will show that the sequence of the solutions of the approximating function converges to the minimum rank solution. On the experimental side, it will be shown that the proposed algorithm, termed SRF standing for Smoothed Rank Function, can recover matrices which are unique solutions of the rank minimization problem and yet not recoverable by nuclear norm minimization. Furthermore, it will be demonstrated that, in completing partially observed matrices, the accuracy of SRF is considerably and consistently better than some famous algorithms when the number of revealed entries is close to the minimum number of parameters that uniquely represent a low-rank matrix.
This paper summarizes the design of a programmable processor with transport triggered architecture (TTA) for decoding LDPC and turbo codes. The processor architecture is designed in such a manner that it can be programmed for LDPC or turbo decoding for the purpose of internetworking and roaming between different networks. The standard trellis based maximum a posteriori (MAP) algorithm is used for turbo decoding. Unlike most other implementations, a supercode based sum-product algorithm is used for the check node message computation for LDPC decoding. This approach ensures the highest hardware utilization of the processor architecture for the two different algorithms. Up to our knowledge, this is the first attempt to design a TTA processor for the LDPC decoder. The processor is programmed with a high level language to meet the time-to-market requirement. The optimization techniques and the usage of the function units for both algorithms are explained in detail. The processor achieves 22.64 Mbps throughput for turbo decoding with a single iteration and 10.12 Mbps throughput for LDPC decoding with five iterations for a clock frequency of 200 MHz.
The ever-increasing demand for broadband Internet access has motivated the further development of the digital subscriber line to the G.fast standard in order to expand its operational band from 106 MHz to 212 MHz. Conventional far-end crosstalk (FEXT) based cancellers falter in the upstream transmission of this emerging G.fast system. In this paper, we propose a novel differential evolution algorithm (DEA) aided turbo channel estimation (CE) and multi-user detection (MUD) scheme for the G.fast upstream including the frequency band up to 212 MHz, which is capable of approaching the optimal Cramer-Rao lower bound of the channel estimate, whilst approaching the optimal maximum likelihood (ML) MUDs performance associated with perfect channel state information, and yet only imposing about 5% of its computational complexity. Explicitly, the turbo concept is exploited by iteratively exchanging information between the continuous value-based DEA assisted channel estimator and the discrete value-based DEA MUD. Our extensive simulations show that 18 dB normalized mean square error gain is attained by the channel estimator and 10 dB signal-to-noise ratio gain can be achieved by the MUD upon exploiting this iteration gain. We also quantify the influence of the CE error, of the copper length and of the impulse noise. Our study demonstrates that the proposed DEA aided turbo CE and MUD scheme is capable of offering near-capacity performance at an affordable complexity for the emerging G.fast systems.
Turbo compressed sensing (Turbo-CS) is an efficient iterative algorithm for sparse signal recovery with partial orthogonal sensing matrices. In this paper, we extend the Turbo-CS algorithm to solve compressed sensing problems involving more general signal structure, including compressive image recovery and low-rank matrix recovery. A main difficulty for such an extension is that the original Turbo-CS algorithm requires prior knowledge of the signal distribution that is usually unavailable in practice. To overcome this difficulty, we propose to redesign the Turbo-CS algorithm by employing a generic denoiser that does not depend on the prior distribution and hence the name denoising-based Turbo-CS (D-Turbo-CS). We then derive the extrinsic information for a generic denoiser by following the Turbo-CS principle. Based on that, we optimize the parametric extrinsic denoisers to minimize the output mean-square error (MSE). Explicit expressions are derived for the extrinsic SURE-LET denoiser used in compressive image denoising and also for the singular value thresholding (SVT) denoiser used in low-rank matrix denoising. We find that the dynamics of D-Turbo-CS can be well described by a scaler recursion called MSE evolution, similar to the case for Turbo-CS. Numerical results demonstrate that D-Turbo-CS considerably outperforms the counterpart algorithms in both reconstruction quality and running time.
Certain binary asymmetric channels, such as Z-channels in which one of the two crossover probabilities is zero, demand optimal ones densities different from 50%. Some broadcast channels, such as broadcast binary symmetric channels (BBSC) where each component channel is a binary symmetric channel, also require a non-uniform input distribution due to the superposition coding scheme, which is known to achieve the boundary of capacity region. This paper presents a systematic technique for designing nonlinear turbo codes that are able to support ones densities different from 50%. To demonstrate the effectiveness of our design technique, we design and simulate nonlinear turbo codes for the Z-channel and the BBSC. The best nonlinear turbo code is less than 0.02 bits from capacity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
