Fast Sampling for Linear Inverse Problems of Vectors and Tensors using Multilinear Extensions

Hao Li, Dong Liang, Zixi Zhou, Zheng Xie

Published 2023-12-04Version 1

Sampling vector and tensor signals is the process of choosing sites in vectors and tensors to place sensors in order to effectively recover the whole signals from a limited number of observations by solving linear inverse problems (LIPs). Here, we present closed-form multilinear extensions for the frame potential of pruned matrices, and based on these, we develop an algorithm named fast Frank-Wolfe algorithm for sampling vectors and tensors with low complexity. Then we provide the approximation factor of our proposed algorithm for a special class of sampling matrices. Then, we conduct experiments to verify the higher performance and lower complexity of our proposed algorithm. Finally, we demonstrate that FFW sampling and least squares reconstruction yield superior results for image data compared to convCNP completion with random sampling.