Disclosed is a method for recovering an original signal in a DS-CDMA system based on complexity reduction. In such a method, first, a partial derivative for rMLL is calculated by using a partial derivative generated by applying fast Fourier transform (FFT) to a reduced negative marginal log likelihood (rMLL) obtained by applying a law of log determinant to a Gaussian process regression (GPR) scheme used for the multi-user detection and thereafter, integrating stochastic gradient descent (SGD). Thereafter, the rMLL is calculated by using the partial derivative for the rMLL and a hyper-parameter is updated to a convergence point until an error gap is converged by repeated calculation of the rMLL. Next, a kernel function used for estimating a matched filter is calculated by using the hyper-parameter estimated through the convergence and the original signal for each of multi-users is recovered by using the kernel function.