Lp-Norm Constrained Coding With Frank-Wolfe Network

Ke Sun, Zhangyang Wang, Dong Liu, Runsheng Liu

Introduction

In signal processing, coding involves representing a signal as a combination of basis vectors. While much research has focused on sparse coding (using $L_0$ or $L_1$ norms), many real-world signals are better represented by non-sparse coding ($L_p$-norm where $p > 1$), which spreads information more evenly across the representation. However, non-sparse coding is mathematically challenging because standard deep learning approaches like LISTA (Learned Iterative Shrinkage-Thresholding Algorithm) rely on Projected Gradient Descent, which requires an analytical projection step that is unavailable for general $L_p$ norms.

The Frank-Wolfe Network (F-W Net) bridges this gap by unrolling the Frank-Wolfe (conditional gradient) optimization algorithm into a trainable neural network. This architecture handles general $L_p$ constraints without complex projection math, offering an interpretable alternative to traditional "black box" neural networks.

The Frank-Wolfe Network Architecture

The core innovation of F-W Net is the mapping of each iteration of the Frank-Wolfe algorithm to a specific layer in a neural network. This "unrolling and truncation" process transforms an iterative solver into a feed-forward structure consisting of an initialization sub-network and a recurrent refinement sub-network.

Architecture of the Frank-Wolfe Network (F-W Net) showing the initialization and recurrent refinement sub-networks.

A key component is the poolp unit, a novel nonlinear unit derived from the Frank-Wolfe linear subproblem. This unit provides a theoretical unification of common deep learning operations:

  • When $p=1$, it functions as max pooling.
  • When $p=2$, it functions as root-mean-square pooling.
  • As $p \to \infty$, it approaches average pooling.

Furthermore, the authors demonstrate that F-W Net can be viewed as a specialized form of Long Short-Term Memory (LSTM) network, where the "gates" are mathematically derived from the Frank-Wolfe update rules rather than being purely heuristic.

Learning the Prior

Unlike traditional optimization where hyperparameters like the norm $p$ and step size $\gamma$ are fixed, F-W Net treats them as learnable parameters. This allows the network to automatically discover the optimal structural priors for a given dataset directly from the data.

Learning dynamics of parameters p and gamma, demonstrating the network's ability to estimate the true p-value of the data.

Experimental results on synthetic data show that the network can accurately estimate the "true" $p$ value of a dataset during training. This capability suggests that F-W Net can be used as a tool for statistical discovery in unknown data distributions. Additionally, the step size $\gamma^t$ is learned per iteration, optimizing the convergence rate beyond what is typically achieved with standard heuristic schedules.

Experimental Results

The authors evaluated F-W Net across several benchmarks, showing significant improvements in both efficiency and accuracy:

  • Efficiency: F-W Net achieved significantly lower Mean Squared Error (MSE) in just 8 iterations compared to the original Frank-Wolfe algorithm.
  • Digit Recognition (MNIST): A 4-layer F-W Net achieved a 1.25% error rate, outperforming a 50-iteration Learned Coordinate Descent (LCoD) model.
  • Image Denoising: On the BSD-500/68 datasets, the Convolutional F-W Net (Conv F-W Net) achieved a PSNR of 31.27 dB (at $\sigma=15$), surpassing baselines like BM3D (31.07 dB) and DnCNN (30.89 dB).
  • Super-Resolution: F-W Net outperformed SRCNN and VDSR on Set-5 and Set-14 benchmarks, demonstrating high flexibility with fewer parameters.

Conclusion

F-W Net provides a mathematically grounded framework for $L_p$-norm constrained coding. By integrating optimization theory with deep learning, it achieves high performance while maintaining interpretability. While currently limited to convex constraints ($p \ge 1$), future work may extend this framework to non-convex cases and more complex structural constraints.

Summary updated

BibTeX
@article{sun2020lp,
  author = {Ke Sun and Zhangyang Wang and Dong Liu and Runsheng Liu},
  title = {{Lp-Norm Constrained Coding With Frank-Wolfe Network}},
  journal = {IEEE Trans. Circuits Syst. Video Technol.},
  year = {2020},
  doi = {10.1109/tcsvt.2019.2936135},
}
Figure