Nonparametric Basis Pursuit via Sparse Kernel-based Learning

Juan Andrés Bazerque, Georgios B. Giannakis

Abstract

This paper introduces Nonparametric Basis Pursuit (NBP), a framework that merges the flexibility of kernel-based learning with the power of sparse signal processing. By treating basis selection as a functional optimization problem in Reproducing Kernel Hilbert Spaces (RKHS), the authors provide a unified toolbox for tasks like multi-kernel selection, dictionary learning, and matrix completion that can incorporate complex prior domain knowledge.

Introduction

Traditional nonparametric regression often falls victim to the "curse of dimensionality"—as the number of input variables grows, the amount of data needed to maintain accuracy explodes. While sparse recovery techniques (like the Lasso or Basis Pursuit) are excellent at finding the "simplest" explanation for data, they are typically parametric. On the other hand, kernel methods are powerful but often lack the ability to perform feature or basis selection automatically.

The NBP framework aims to bridge this gap, creating a system that can handle high-dimensional data, missing entries, and model uncertainty by leveraging both the "kernel trick" and sparsity-inducing norms.

Methodology

The core of the NBP approach is modeling a target function $f(x, y)$ as a sum of components: $$f(x, y) = \sum_{i=1}^{P} c_i(x)b_i(y)$$ where $b_i(y)$ are prescribed bases and $c_i(x)$ are unknown coefficient functions.

Functional Sparsity and the Representer Theorem

Key technical contributions include the use of a group-Lasso-like penalty on the RKHS norms of $c_i(x)$ to force unimportant bases to zero. The authors prove an extension of the Representer Theorem, showing that even in this complex additive setup, the optimal functions still have a finite-dimensional representation, making the problem computationally tractable.

Blind NBP (Kernel Matrix Completion)

The model extends to "Blind NBP," where neither the bases nor the coefficients are known. This results in a kernelized version of matrix completion that uses kernels to model correlations across both rows (e.g., users) and columns (e.g., items). This allows the model to "borrow" information from correlated entries to reconstruct entirely missing rows or columns.

The Blind NBP framework for kernel matrix completion, illustrating the factorization of the target matrix into basis and coefficient components.

Experimental Evaluation

The framework was validated across three distinct scenarios:

  1. Cognitive Radio Sensing: A simulated environment with 100 radios measuring RF power spectral density across space and frequency to map "spectrum holes."
  2. Yeast Microarray Data: A real dataset of 4,772 genes sampled at 13 time points, testing imputation of missing data.
  3. Abilene Network (Internet 2): Real traffic load data from a backbone network used for predicting future traffic flows.

Results and Discussion

The NBP approach demonstrates significant improvements over standard methods by exploiting underlying spatial or temporal smoothness.

Spectrum Mapping

In the spectrum cartography example, the authors use Multi-Kernel Learning (MKL) to combine a "coarse" kernel (for pathloss) and a "fine" kernel (for shadowing). This allows the model to capture physical phenomena at different scales simultaneously. The NBP-MKL hybrid correctly identified occupied frequency bands and successfully separated smooth pathloss effects from jagged shadowing effects.

Spectrum mapping results showing the spatial power distribution (left) and the recovered power spectral density across frequency (right).

Matrix Imputation and Network Prediction

  • Microarray Imputation: In a test with 90% missing data, Blind NBP achieved a recovery error of -8dB and successfully recovered 25 completely missing rows, where standard nuclear-norm methods failed.
  • Network Prediction: For the Abilene network, the NBP approach reduced relative prediction error to 0.15, compared to 0.22 for standard independent LMMSE estimators, by exploiting network topology via the kernel.

Conclusion

Nonparametric Basis Pursuit provides a powerful framework for sparse functional estimation. While computational scaling for very large datasets remains a challenge due to Gram matrix size, the method's ability to incorporate domain knowledge via kernels offers a significant advantage in data-sparse or high-dimensional regimes. Future work includes generalizing the framework to tensor completion and exploring dictionary-based variants for improved scalability.

Summary updated

Abstract

Signal processing tasks as fundamental as sampling, reconstruction, minimum mean-square error interpolation and prediction can be viewed under the prism of reproducing kernel Hilbert spaces. Endowing this vantage point with contemporary advances in sparsity-aware modeling and processing, promotes the nonparametric basis pursuit advocated in this paper as the overarching framework for the confluence of kernel-based learning (KBL) approaches leveraging sparse linear regression, nuclear-norm regularization, and dictionary learning. The novel sparse KBL toolbox goes beyond translating sparse parametric approaches to their nonparametric counterparts, to incorporate new possibilities such as multi-kernel selection and matrix smoothing. The impact of sparse KBL to signal processing applications is illustrated through test cases from cognitive radio sensing, microarray data imputation, and network traffic prediction.
BibTeX
@inproceedings{bazerque2013nonparametric,
  author = {Juan Andrés Bazerque and Georgios B. Giannakis},
  title = {{Nonparametric Basis Pursuit via Sparse Kernel-based Learning}},
  booktitle = {IEEE Signal Process. Mag},
  year = {2013},
  url = {https://openreview.net/forum?id=MC3B2Vh9-lN},
}
Figure