We study the spectral recovery problem for dynamical sampling on a finite cyclic grid. Given time snapshots obtained from a fixed uniform spatial subsampling of the orbit $x_{\ell}=A^{\ell}f$, we aim to recover the spectrum of the unknown circular convolution operator $A$. However, in the presence of outliers, even in only a few snapshots, existing approaches often struggle to recover the spectrum. We address this challenge by proposing a novel robust spectral recovery model in the presence of time-sparse corruptions. We propose a robust pipeline that lifts the problem to a sequence of robust low-rank Hankel recovery and completion tasks, followed by Prony-type spectral estimation. Numerical experiments confirm the accurate spectral recovery of the proposed approach and exhibit its superior robustness against state-of-the-art under various settings.

This paper investigates the problem of dynamical sampling for graph signals influenced by a constant source term. We consider signals evolving over time according to a linear dynamical system on a graph, where both the initial state and the source term are bandlimited. We introduce two random space-time sampling regimes and analyze the conditions under which stable recovery is achievable. While our framework extends recent work on homogeneous dynamics, it addresses a fundamentally different setting where the evolution includes a constant source term. This results in a non-orthogonal-diagonalizable system matrix, rendering classical spectral techniques inapplicable and introducing new challenges in sampling design, stability analysis, and joint recovery of both the initial state and the forcing term. A key component of our analysis is the spectral graph weighted coherence, which characterizes the interplay between the sampling distribution and the graph structure. We establish sampling complexity bounds ensuring stable recovery via the Restricted Isometry Property (RIP), and develop a robust recovery algorithm with provable error guarantees. The effectiveness of our method is validated through extensive experiments on both synthetic and real-world datasets.

Low-rank decomposition (LRD) and pruning-based methodologies are usually applied to compress neural networks. When targeting a large compression ratio in one shot, LRD-based methods such as truncated SVD and CUR can suffer from serious degradations in performance and also difficulties in recovering the performance. To this end, a new promising method ICURA (Iterative CUR Approximations) is developed here for the neural network compression by integrating the retraining into CUR in an iterative manner and tailored gradient approximation scheme for accelerating the retraining as enlightened by recent theoretical advances in CUR decompositions, where the rank of CUR approximation gradually decreases (but not a large sudden decrease in rank) to approximate the weight matrices of the network and a retraining step is performed after each rank reduction. Experiments are conducted on widely used datasets and neural network architectures, and the results suggest that ICURA can achieve a notably higher accuracy than classical LRD-based methods, especially when a large compression ratio is expected. For example, ICURA needs about 30 % fewer parameters than truncated SVD and still outperforms it in accuracy when compressing ResNet-56 on CIFAR-100. In comparison with a recent low-rank method called LC, ICURA can achieve an accuracy that is$\mathbf{4. 1 2 \%}$higher while compressing ResNet-56 to the same compression ratio.

Tensor dimensionality reduction is one of the fundamental tools for modern data science. To address the high computational overhead, fiber-wise sampled subtensors that preserve the original tensor rank are often used in designing efficient and scalable tensor dimensionality reduction. However, the theory of property inheritance for subtensors is still underdevelopment, that is, how the essential properties of the original tensor will be passed to its subtensors. This paper theoretically studies the property inheritance of the two key tensor properties, namely incoherence and condition number, under the tensor train setting. We also show how tensor train rank is preserved through fiberwise sampling. The key parameters introduced in theorems are numerically evaluated under various settings. The results show that the properties of interest can be well preserved to the subtensors formed via fiber-wise sampling. Overall, this paper provides several handy analytic tools for developing efficient tensor analysis methods.

We study the problem of symmetric positive semi-definite low-rank matrix completion (MC) with deterministic entry-dependent sampling. In particular, we consider rectified linear unit (ReLU) sampling, where only positive entries are observed, as well as a generalization to threshold-based sampling. We first empirically demonstrate that the landscape of this MC problem is not globally benign: Gradient descent (GD) with random initialization will generally converge to stationary points that are not globally optimal. Nevertheless, we prove that when the matrix factor with a small rank satisfies mild assumptions, the nonconvex objective function is geodesically strongly convex on the quotient manifold in a neighborhood of a planted low-rank matrix. Moreover, we show that our assumptions are satisfied by a matrix factor with i.i.d. Gaussian entries. Finally, we develop a tailor-designed initialization for GD to solve our studied formulation, which empirically always achieves convergence to the global minima. We also conduct extensive experiments and compare MC methods, investigating convergence and completion performance with respect to initialization, noise level, dimension, and rank.

Abstract. We study the tensor robust principal component analysis (TRPCA) problem, a tensorial extension of matrix robust principal component analysis, which aims to split the given tensor into an underlying low-rank component and a sparse outlier component. This work proposes a fast algorithm, called robust tensor CUR decompositions (RTCUR), for large-scale nonconvex TRPCA problems under the Tucker rank setting. RTCUR is developed within a framework of alternating projections that projects between the set of low-rank tensors and the set of sparse tensors. We utilize the recently developed tensor CUR decomposition to substantially reduce the computational complexity in each projection. In addition, we develop four variants of RTCUR for different application settings. We demonstrate the effectiveness and computational advantages of RTCUR against state-of-the-art methods on both synthetic and real-world datasets.

Tensor completion is an important problem in modern data analysis. In this work, we investigate a specific sampling strategy, referred to as tubal sampling. We propose two novel non-convex tensor completion frameworks that are easy to implement, named tensor L1-L2(TL12) and tensor completion via CUR (TCCUR). We test the efficiency of both methods on synthetic data and a color image inpainting problem. Empirical results reveal a trade-off between the accuracy and time efficiency of these two methods in a low sampling ratio. Each of them outperforms some classical completion methods in at least one aspect.

We consider the space-time sampling and reconstruction of sparse bandlimited graph signals driven by a heat diffusion process. In this paper, we develop a sampling framework consisting of selecting a small subset of space-time nodes at random according to some probability distribution, generalizing the classical variable density sampling to the heat diffusion field. We show that the number of space-time samples required to ensure stable recovery depends on an incoherence parameter determined by the interplay between graph topology, temporal dynamics, and sampling probability distributions. In optimal scenarios, as few as $\mathcal{O}\left( {s\log k} \right)$ space-time samples are sufficient to ensure accurate recovery of all k-bandlimited graph signals that are additionally s-sparse. Our proposed sampling method requires much fewer spatial samples than the static case by leveraging temporal information. Finally, we test our sampling techniques on a wide variety of graphs. The numerical results on synthetic and real climate data sets support our theoretical findings and demonstrate the practical applicability.

Band selection is an important technique for eliminating spectral redundancy of hyperspectral imagery (HSI) while preserving critical information. Recently, correlations among neighboring bands or pixels have been exploited in the form of graph regularizations to reduce the data dimensionality efficiently. However, manipulation of graph regularizations typically causes computational bottlenecks. In this work, we propose a robust method for hyperspectral band selection based on spatial/spectral graph Laplacians and matrix CUR decomposition. The efficiency of the proposed method has been shown on two real data sets by comparing with several other state-of-the-art band selection methods.

While uniform sampling has been widely studied in the matrix completion literature, CUR sampling approximates a low-rank matrix via row and column samples. Unfortunately, both sampling models lack flexibility for various circumstances in real-world applications. In this work, we propose a novel and easy-to-implement sampling strategy, coined Cross-Concentrated Sampling (CCS). By bridging uniform sampling and CUR sampling, CCS provides extra flexibility that can potentially save sampling costs in applications. In addition, we also provide a sufficient condition for CCS-based matrix completion. Moreover, we propose a highly efficient non-convex algorithm, termed Iterative CUR Completion (ICURC), for the proposed CCS model. Numerical experiments verify the empirical advantages of CCS and ICURC against uniform sampling and its baseline algorithms, on both synthetic and real-world datasets.

Low rank tensor approximation is a fundamental tool in modern machine learning and data science. In this paper, we study the characterization, perturbation analysis, and an efficient sampling strategy for two primary tensor CUR approximations, namely Chidori and Fiber CUR. We characterize exact tensor CUR decompositions for low multilinear rank tensors. We also present theoretical error bounds of the tensor CUR approximations when (adversarial or Gaussian) noise appears. Moreover, we show that low cost uniform sampling is sufficient for tensor CUR approximations if the tensor has an incoherent structure. Empirical performance evaluations, with both synthetic and real-world datasets, establish the speed advantage of the tensor CUR approximations over other state-of-the-art low multilinear rank tensor approximations.

This paper considers the use of robust principal component analysis (RPCA) in a CUR decomposition framework and applications thereof. Our main algorithms produce a robust version of column-row factorizations of matrices $D=L+S$, where $L$ is low-rank and $S$ contains sparse outliers. These methods yield interpretable factorizations at low computational cost and provide new CUR decompositions that are robust to sparse outliers, in contrast to previous methods. We consider two key imaging applications of RPCA: video foreground-background separation and face modeling. This paper examines the qualitative behavior of our robust CUR decompositions on the benchmark videos and face datasets and finds that our method works as well as standard RPCA while being significantly faster. Additionally, we consider hybrid randomized and deterministic sampling methods which produce a compact CUR decomposition of a given matrix and apply this to video sequences to produce canonical frames thereof.

Robust principal component analysis (RPCA) is a widely used tool for dimension reduction. In this work, we propose a novel non-convex algorithm, coined Iterated Robust CUR (IRCUR), for solving RPCA problems, which dramatically improves the computational efficiency in comparison with the existing algorithms. IRCUR achieves this acceleration by employing CUR decomposition when updating the low rank component, which allows us to obtain an accurate low rank approximation via only three small submatrices. Consequently, IRCUR is able to process only the small submatrices and avoid the expensive computing on full matrix through the entire algorithm. Numerical experiments establish the computational advantage of IRCUR over the state-of-art algorithms on both synthetic and real-world datasets.

The paper is devoted to the normal tiling whose tiles are uniformly bounded and general connected closed sets instead of being restricted to polytopes or convex sets. We estimate the number of neighbors of a tile in the normal tiling and develop various novel techniques to derive lower and upper bounds. The bounds for lattice tilings are shown to be optimal.