PaperlayerView exact revision on arXiv

Source-linked AI summary

Smooth PARAFAC Decomposition for Tensor Completion

Tatsuya Yokota, Qibin Zhao, Andrzej Cichocki

arXiv:1505.06611v3cs.CV

TL;DR

Low-rank tensor models alone may be insufficient for recovering visual data with very high missingness. The paper proposes smooth PARAFAC tensor completion with TV or QV constraints and gradual rank selection, and reports improvements over state-of-the-art methods on visual and other completion tasks.

  • Problem

    Low-rank assumptions alone are insufficient for recovering visual data such as color and 3D images when missing-data ratios are extremely high.

  • Method

    SPC combines smooth PARAFAC decomposition with TV or QV constraints on latent components and increases the component count gradually to select rank.

  • Results

    SPC outperformed state-of-the-art methods, particularly HaLRTC, STDC, and FBCP-MP, with strong visual-data results under high missingness.

  • Takeaways & Limitations

    Integrating latent-component smoothness with adaptive rank selection yields an effective tensor-completion approach for visual data.

Abstract

from arXiv · show

In recent years, low-rank based tensor completion, which is a higher-order extension of matrix completion, has received considerable attention. However, the low-rank assumption is not sufficient for the recovery of visual data, such as color and 3D images, where the ratio of missing data is extremely high. In this paper, we consider "smoothness" constraints as well as low-rank approximations, and propose an efficient algorithm for performing tensor completion that is particularly powerful regarding visual data. The proposed method admits significant advantages, owing to the integration of smooth PARAFAC decomposition for incomplete tensors and the efficient selection of models in order to minimize the tensor rank. Thus, our proposed method is termed as "smooth PARAFAC tensor completion (SPC)." In order to impose the smoothness constraints, we employ two strategies, total variation (SPC-TV) and quadratic variation (SPC-QV), and invoke the corresponding algorithms for model learning. Extensive experimental evaluations on both synthetic and real-world visual data illustrate the significant improvements of our method, in terms of both prediction performance and efficiency, compared with many state-of-the-art tensor completion methods.

I. INTRODUCTION

Tensor completion extends matrix completion to multidimensional data, but visual data can require exploiting both low-rank structure and smoothness. The paper introduces smoothness-aware tensor completion and adaptive rank selection for difficult visual-data settings.

  • Tensor completion estimates missing multidimensional-array entries from observed values and structural properties such as correlations, symmetry, continuity, or repetition.
  • Color images are third-order tensors and color videos are fourth-order tensors, but separate matrix completion of color frames neglects their natural multidimensional structure.
  • Existing tensor-completion approaches primarily exploit low-rank structure through nuclear-norm minimization, Tucker decomposition, or low-rank PD models.
  • Smoothness helps preserve smooth image content and remove non-smooth noise, motivating its integration with PD-based tensor completion.
  • The paper imposes smoothness on latent component vectors using total variation and a stronger quadratic-variation constraint, with different levels enforced adaptively across components.
  • The proposed rank-selection strategy increases tensor rank from one step by step because smoothness makes a fixed upper bound difficult to determine.

III. PROPOSED NEW METHOD

The proposed method combines PARAFAC decomposition with smoothness constraints for tensor completion. Smooth feature vectors reduce decomposition flexibility, so the method avoids prespecifying a rank upper bound and increases the number of components gradually.

  • The paper proposes a PARAFAC decomposition algorithm for tensor completion with smoothness constraints.
  • In the PD model, components are outer products of feature vectors with scaling multipliers, and the smallest component count representing the tensor defines its rank.
  • Imposing smoothness on feature vectors increases the required component count because the constraint reduces decomposition flexibility.
  • SPC increases the number of components from R = 1 to its optimal value, eliminating the need to determine an upper bound for tensor rank.

A. Fundamental Problem for the Fixed Rank SPC (FR-SPC)

FR-SPC completes tensors by fitting a smooth PD approximation on observed entries and using that approximation for missing entries. Its objective combines reconstruction error with component smoothness, supporting TV or QV regularization and adaptive component smoothing.

  • FR-SPC formulates fixed-rank tensor completion by optimizing PD factors and scaling parameters under a specified component count.
  • The completed tensor preserves observed entries from the input and fills unobserved entries with the smooth PD approximation.
  • The parameter p selects the smoothness type, while ρ and L^(n) control mode-specific smoothness penalties based on neighboring factor-vector differences.
  • The reconstruction term measures observed-entry mean squared error, while the penalty term enforces smooth component vectors.
  • p = 1 yields total variation and p = 2 yields quadratic variation, with the constraint applied to latent feature vectors rather than the output surface.
  • The implementation alternates factor updates and reconstructs observed and missing portions until the change in reconstruction error is sufficiently small.

B. Derivation of the FR-SPC Algorithm

FR-SPC solves the smooth fixed-rank objective through feature-wise alternating updates, using gradient or sub-gradient normalization for both QV and TV penalties. Model selection then increases rank until observed-entry error reaches a target threshold.

  • B. Derivation of the FR-SPC Algorithm: HALS solves the FR-SPC objective through feature-wise block-coordinate updates while treating each unit-norm constraint separately.
  • B. Derivation of the FR-SPC Algorithm: The factor-vector update uses gradient descent for QV and sub-gradient descent for TV, with normalization enforcing unit-norm constraints.
  • B. Derivation of the FR-SPC Algorithm: The algorithm repeats updates until convergence, although global convergence is not generally guaranteed for the factor sub-optimization.
  • C. Model Selection for the Number of Components R: Model selection starts at R = 1, runs FR-SPC, and increases R until the observed-entry residual satisfies a threshold based on SDR.
  • B. Derivation of the FR-SPC Algorithm: The scaling-factor update is obtained analytically because its local optimization problem is unconstrained and quadratic.

C. Model Selection for the Number of Components R

SPC selects the number of smooth PARAFAC components by increasing the rank from one until a sufficient fit is achieved, using an accelerated stopping rule. The method accepts redundant terms because smooth PD approximation can be ill-posed.

  • The model-selection problem balances underfitting from too few components against overfitting from too many.
  • SPC formulates rank selection by gradually increasing R until the smooth PD model reaches an error bound ε.The solution space S(R, p, ρ) contains tensors spanned by R smooth components.
  • The accelerated algorithm stops iterations early when convergence slows, then increases R and reruns optimization for the larger rank.This replaces the more time-consuming direct procedure for estimating R.
  • The optimization starts at rank one and progressively increases R until the fitting criterion is satisfied.
  • Because smooth PD approximation may be ill-posed, SPC allows redundant components and prioritizes good approximation over minimum-rank decomposition.

IV. EXPERIMENTAL RESULTS

The experiments evaluate SPC-TV and SPC-QV on synthetic and real-world visual datasets, testing parameter sensitivity and comparing the methods with four state-of-the-art tensor completion algorithms.

  • The evaluation uses one synthetic dataset and several real-world visual datasets to assess parameter sensitivity and comparative performance.
  • Figure 3 examines convergence behavior and component-count changes under 80% missing voxels for multiple stopping thresholds and TV/QV smoothing settings.
  • The comparisons include LTVNN, HaLRTC, STDC, and FBCP-MP as state-of-the-art baselines.

A. Convergence Properties Using a Synthetic Third-Order Tensor

On a synthetic third-order tensor with 80% missing voxels, SPC evaluates completion behavior through iso-surface visualization and convergence of error and estimated rank.

  • The synthetic tensor combines four multidimensional Gaussian functions, with 80% of voxels randomly removed before completion.
  • Figure 3 tracks MSE between observed entries and estimates together with the number of components R across SPC iterations.
  • Figure 7 compares PSNR and SSIM differences from the LTVNN baseline across benchmark images, missing rates from 60% to 95%, and five completion methods.

B. Color Image Completion

The color-image experiment evaluates completion on ten 256 × 256 × 3 images under missing rates from 60% to 95%, including dead-pixel cases, using PSNR and SSIM.

  • The study applies proposed and existing methods to 10 color images sized 256 × 256 × 3.
  • Random element deletion produces missing ratios of 60%, 70%, 80%, 90%, and 95%.
  • For “Giant” and “Wasabi,” all color elements of individual pixels are deleted at every missing ratio.
  • Completion quality is measured with PSNR and SSIM, with SSIM incorporating local-block averages and variances to assess visual quality.

1) Convergence Behavior of SPC and FR-SPC Algorithms:

SPC achieved better convergence outcomes than FR-SPC under the tested Lena completion setting, while SPC smoothing performance varied with the parameter ρ.

  • SPC achieved significantly better PSNR and SSIM values than FR-SPC across 10 random initializations on Lena with 95% pixels missing.Both methods used p = 2 and ρ = [0.5, 0.5, 0], with the same number of components.
  • FR-SPC converged to local minima larger than SPC’s convergence points under the tested completion setting.
  • The rank-increasing approach produced an algorithm that converged to better local minima.
  • Larger ρ values considerably increased PSNR and SSIM for the QV/TV smoothing algorithms in the parameter study.The study used Lena with 80% pixels missing and tested τ ∈ [0.05, 0.95], with ρ := τ/(1−τ).

3) Comparison with the State-of-the-Art Methods:

Across visual completion experiments, smoothness-based methods generally improved structural similarity, while SPC-QV showed the strongest reported benchmark performance and robustness at extreme missing rates.

  • The benchmark evaluation used proposed TV and QV methods alongside four state-of-the-art methods on 10 color images with varied random missing ratios.
  • Fig. 8 compares incomplete and reconstructed images for text masking, scratches, random dead pixels, and random voxel missingness at 95% and 99%.The incomplete images appear in the first column and reconstructions in the remaining columns.
  • SPC-QV considerably outperformed all existing methods across the 10 benchmark images.SPC-TV was inferior to STDC and FBCP-MP in most cases, whereas smooth methods generally scored better by SSIM than PSNR.
  • At a 99% missing ratio, only FBCP-MP and SPC-QV produced recognizable Lena shapes, with SPC-QV performing better.
  • For random missing pixels or voxels, performance differences became significant as the missing ratio increased.

C. MRI Image Completion

The paper evaluates smooth tensor completion on MRI, color-image, and CMU-face data, emphasizing high-missingness recovery and component-level smoothness in SPC.

  • C. MRI Image Completion: The color-image tests used 256 × 256 images represented as three red, green, and blue layers.
  • The reported experiments include 256 × 256 color images, MRI 3D images, and fourth-order CMU facial data.
  • C. MRI Image Completion: SPC significantly outperformed other methods in SDR while completing MRI 3D images with 90%-95% of voxels missing.MRI images had size 109 × 91 × 91 and were evaluated across missing rates from 60% to 95%.
  • D. 4th-order Tensor Completion Using a CMU Faces Dataset: For CMU faces with 80% of faces missing, HaLRTC failed, STDC produced broken faces, and SPC achieved excellent results.
  • A. Smooth PARAFAC Decomposition Model: SPC enforces local similarity between neighboring elements within each component factor matrix, unlike methods smoothing the output matrix or similarities between components.
  • A. Smooth PARAFAC Decomposition Model: Adaptive smoothness assigns different smoothness levels to components, building smooth images from components ordered from smoothest to less smooth.

B. TV Smoothing and QV Smoothing

SPC combines smoothness constraints with PARAFAC tensor completion and selects rank by increasing components until the optimal rank is reached. The paper contrasts TV and QV smoothing, while emphasizing QV’s stronger behavior for image completion.

  • QV smoothing: The authors report that QV performs better than TV for image completion, despite TV often being preferred for image denoising and restoration.They identify this as a new finding for image completion research.
  • QV smoothing: QV smoothing yields a unique interpolating solution for the illustrated signal, whereas TV permits multiple solutions and may produce bumps.For z = [0, NaN, 2, NaN, 0]^T, QV gives [0, 1, 2, 1, 0]^T, while TV allows a,b ∈ [0,2].
  • Rank selection: Rank-increasing selection also supports initialization because optimization can contain multiple local minima whose outcomes depend on initialization.The paper presents this motivation alongside the SPC optimization process shown in Fig. 1.
  • Rank selection: The proposed SPC method uses TV and QV constraints and increases rank gradually rather than requiring a prior tensor-rank upper bound.The rank-increasing strategy is intended for smooth models whose required component count depends on the imposed smoothness level.
  • Evaluation: SPC is reported to outperform HaLRTC, STDC, and FBCP-MP in experiments, while rank-increasing approaches are described as efficient for large-scale and ill-posed settings.The conclusion summarizes the comparison with these state-of-the-art tensor completion algorithms.
Loading 1505.06611v3…