Accurate recovery of high-dimensional tensor data from incomplete observations remains a critical challenge in data-driven applications. To overcome the inherent limitations of convex surrogates for tensor rank and sparsity approximation, we introduce a Tucker decomposition-based method that employs non-convex approximations inspired by Laplace-like functions. The Tucker framework effectively captures mode-specific complexity through its flexible core tensor and computable multidimensional rank, demonstrating advantages over alternative high-order decompositions. Specifically, we define novel non-convex surrogates: the \(\varepsilon \) -norm for the Tucker rank and the \(L_\varepsilon \) -norm for the \(\ell _0\) -norm (sparsity), with the parameter \(\varepsilon \) controlling approximation accuracy. Crucially, the \(L_\varepsilon \) -norm promotes sparser solutions than the \(\ell _1\) -norm under identical constraints. Additionally, we incorporate mode-unfolding regularization terms to exploit inherent structural properties, such as modal smoothness and continuity, commonly found in real-world tensor data. To solve the resulting regularized non-convex and non-smooth optimization model, we develop an efficient hybrid algorithm integrating the Alternating Direction Method of Multipliers (ADMM) and the Majorization-Minimization (MM) framework and establish its convergence to a local stationary point under certain assumptions. Extensive experiments on real-world color image and video datasets validate the superior performance and robustness of our method, particularly in scenarios involving video data with consecutive frame losses where missing entries form a small yet structurally disruptive tensor.
