Abstract: Based on sparse and redundant representation, parallel coordinate descent (PCD) is one of the best denoising algorithms. In audio signal processing, however, when the number of segmented frames is large, the computational burden is heavy. Processing each frame separately with the PCD algorithm causes a dramatic increase in time cost. Therefore, this paper proposes a new time-domain framework and a heuristic joint PCD (called joint-PCD) algorithm based on joint sparse representation (JSR) and simultaneous sparse approximation (SSA). In this framework, each audio frame is used as a column vector to generate a signal matrix. Utilizing an over-complete dictionary, joint-PCD is used to synchronously (simultaneously) denoise a signal matrix (instead of an audio frame), which greatly improves the efficiency of the algorithm and reduces the burden of running time. The simulation results show that the joint-PCD algorithm not only has almost the same and excellent denoising performance with PCD, but also increases the denoising speed of PCD by about five times, which greatly improves the convergence performance of the PCD algorithm.