Frank-Wolfe Network: An Interpretable Deep Structure for Non-Sparse Coding

Dong Liu, Ke Sun, Zhangyang Wang, Runsheng Liu, Zheng-Jun Zha

Abstract

Deep learning architectures often lack interpretability, functioning as "black boxes." This paper introduces the Frank-Wolfe Network (F-W Net), an interpretable deep structure derived by unrolling the Frank-Wolfe optimization algorithm for $L_p$-norm constrained coding. Unlike traditional sparse coding ($p \le 1$), F-W Net focuses on non-sparse cases ($p > 1$). By introducing a novel learnable nonlinear unit, pool_p, which unifies pooling, activation, and normalization, the network achieves superior performance in tasks like image denoising and super-resolution while maintaining mathematical transparency.

Introduction

In signal processing, coding involves transforming a signal into a representation that satisfies specific constraints. While sparse coding (using $L_0$ or $L_1$ norms) has been extensively studied, many real-world signals are better represented through non-sparse coding ($p > 1$), where information is distributed more evenly across the representation. However, solving $L_p$-norm constrained problems is computationally challenging because standard projection-based methods lack simple analytical solutions for general $p$.

To address this, the authors propose the Frank-Wolfe Network (F-W Net). By "unrolling" the Frank-Wolfe optimization algorithm into a neural network architecture, they create a model that is both fast and interpretable, with structural priors that heuristic models lack.

Methodology

The F-W Net is constructed by mapping $T$ iterations of the Frank-Wolfe algorithm to a $T$-layer feed-forward network. This "unrolling" allows the network to learn optimal parameters via backpropagation, compensating for the truncation error of using a small number of iterations.

The pool_p Unit

The core innovation is the pool_p unit, a nonlinear operator derived from the Frank-Wolfe linear minimizer. It consists of two steps:

  1. p-conjugate normalization: Normalization based on the Hölder conjugate of $p$.
  2. p-exponential neuron: An element-wise activation function parameterized by $p$.

This unit is significant because it unifies several classic operations: it behaves like max-pooling when $p=1$, root-mean-square pooling when $p=2$, and average pooling as $p \to \infty$.

The architecture of F-W Net, consisting of a single-layer initialization sub-network followed by a recurrent refinement sub-network.

Learnable Hyper-parameters

Unlike traditional iterative algorithms where parameters like the norm $p$ and step size $\gamma$ are fixed, F-W Net treats them as learnable. This allows the network to discover the most appropriate $L_p$ prior for a given dataset automatically. For image-based tasks, the architecture is extended to a Convolutional F-W Net, where fully connected layers are replaced by convolutional layers.

Experimental Results

The F-W Net was evaluated on synthetic data, MNIST digit recognition, image denoising (BSD-500/68), and super-resolution (Set-5/14).

  • Convergence and Accuracy: On synthetic data, F-W Net converged significantly faster than the original Frank-Wolfe algorithm and outperformed LISTA.
  • Image Restoration: A 4-layer Convolutional F-W Net outperformed the classic BM3D algorithm and a 4-layer DnCNN in denoising tasks. In super-resolution, it achieved higher PSNR/SSIM scores than SRCNN and VDSR by learning the optimal $p$ value.
Comparison of training error over epochs (a) and testing error across different iterations T (b) for F-W Net and baseline methods.

Conclusion

The Frank-Wolfe Network bridges the gap between optimization theory and deep learning. By unrolling a projection-free algorithm, the authors developed an interpretable architecture that excels at non-sparse coding tasks. While currently limited to convex sets ($p \ge 1$), future work aims to extend this framework to non-convex cases and other structural constraints like low-rank priors.

Summary updated

Abstract

The problem of L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> -norm constrained coding is to convert signal into code that lies inside an L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> -ball and most faithfully reconstructs the signal. Previous works under the name of sparse coding considered the cases of L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub> and L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> norms. The cases with p > 1 values, i.e. non-sparse coding studied in this paper, remain a difficulty. We propose an interpretable deep structure namely Frank-Wolfe Network (F-W Net), whose architecture is inspired by unrolling and truncating the FrankWolfe algorithm for solving an L p-norm constrained problem with p ≥ 1. We show that the Frank-Wolfe solver for the L p-norm constraint leads to a novel closed-form nonlinear unit, which is parameterized by p and termed pool p. The pool p unit links the conventional pooling, activation, and normalization operations, making F-W Net distinct from existing deep networks either heuristically designed or converted from projected gradient descent algorithms. We further show that the hyper-parameter p can be made learnable instead of pre-chosen in F-W Net, which gracefully solves the non-sparse coding problem even with unknown p. We evaluate the performance of F-W Net on an extensive range of simulations as well as the task of handwritten digit recognition, where F-W Net exhibits strong learning capability. We then propose a convolutional version of FW Net, and apply the convolutional F-W Net into image denoising and super-resolution tasks, where F-W Net all demonstrates impressive effectiveness, flexibility, and robustness.
BibTeX
@article{liu2020frank,
  author = {Dong Liu and Ke Sun and Zhangyang Wang and Runsheng Liu and Zheng-Jun Zha},
  title = {{Frank-Wolfe Network: An Interpretable Deep Structure for Non-Sparse Coding}},
  journal = {IEEE Trans. Circuits Syst. Video Technol.},
  year = {2020},
  doi = {10.1109/tcsvt.2019.2936135},
}
Figure