In this paper, we focus on a matrix factorization-based approach for robust recovery of low-rank asymmetric matrices from corrupted measurements. We propose an Overparameterized Preconditioned Subgradient Algorithm (OPSA) and provide, for the first time in the literature, linear convergence rates independent of the rank of the sought asymmetric matrix in the presence of gross corruptions. Our work goes beyond existing results in preconditioned-type approaches addressing their current limitation, i.e., the lack of convergence guarantees in the case of asymmetric matrices of unknown rank. By applying our approach to (robust) matrix sensing, we highlight its merits when the measurement operator satisfies a mixed-norm restricted isometry property. Lastly, we present extensive numerical experiments that validate our theoretical results and demonstrate the effectiveness of our approach for different levels of overparameterization and corruption from outliers.

We introduce FedGVI, a probabilistic Federated Learning (FL) framework that is robust to both prior and likelihood misspecification. FedGVI addresses limitations in both frequentist and Bayesian FL by providing unbiased predictions under model misspecification, with calibrated uncertainty quantification. Our approach generalises previous FL approaches, specifically Partitioned Variational Inference (Ashman et al., 2022), by allowing robust and conjugate updates, decreasing computational complexity at the clients. We offer theoretical analysis in terms of fixed-point convergence, optimality of the cavity distribution, and provable robustness to likelihood misspecification. Further, we empirically demonstrate the effectiveness of FedGVI in terms of improved robustness and predictive performance on multiple synthetic and real world classification data sets.

The goal of continual learning is to find a model that solves multiple learning tasks which are presented sequentially to the learner. A key challenge in this setting is that the learner may "forget" how to solve a previous task when learning a new task, a phenomenon known as catastrophic forgetting. To address this challenge, many practical methods have been proposed, including memory-based, regularization-based and expansion-based methods. However, a rigorous theoretical understanding of these methods remains elusive. This paper aims to bridge this gap between theory and practice by proposing a new continual learning framework called "Ideal Continual Learner" (ICL), which is guaranteed to avoid catastrophic forgetting by construction. We show that ICL unifies multiple well-established continual learning methods and gives new theoretical insights into the strengths and weaknesses of these methods. We also derive generalization bounds for ICL which allow us to theoretically quantify "how rehearsal affects generalization". Finally, we connect ICL to several classic subjects and research topics of modern interest, which allows us to make historical remarks and inspire future directions.

The so-called block-term decomposition (BTD) tensor model has been recently receiving increasing attention due to its enhanced ability of representing systems and signals that are composed of blocks of rank higher than one, a scenario encountered in numerous and diverse applications. In this paper, BTD is employed for the completion of a tensor from its partially observed entries. A novel method is proposed, which is based on the idea of imposing column sparsity jointly on the BTD factors and in a hierarchical manner. This way the number of block terms and their ranks can also be estimated, as the numbers of factor columns of non-negligible magnitude. Following a block successive upper bound minimization (BSUM) approach with appropriate choice of the surrogate majorizing functions is shown to result in an alternating hierarchical iteratively reweighted least squares (HIRLS) algorithm, which is fast converging and enjoys high computational efficiency, as it relies in its iterations on small-sized sub-problems with closed-form solutions. Simulation results with both synthetic and real data are reported, which demonstrate the effectiveness of the proposed scheme.

The Schatten-$p$ quasi-norm with $p\in(0,1)$ has recently gained considerable attention in various low-rank matrix estimation problems offering significant benefits over relevant convex heuristics such as the nuclear norm. However, due to the nonconvexity of the Schatten-$p$ quasi-norm, minimization suffers from two major drawbacks: 1) the lack of theoretical guarantees and 2) the high computational cost which is demanded for the minimization task even for trivial tasks such as finding stationary points. In an attempt to reduce the high computational cost induced by Schatten-$p$ quasi-norm minimization, variational forms, which are defined over smaller-size matrix factors whose product equals the original matrix, have been proposed. Here, we propose and analyze a novel {\it variational form of Schatten-$p$ quasi-norm} which, for the first time in the literature, is defined for any continuous value of $p\in(0,1]$ and decouples along the columns of the factorized matrices. The proposed form can be considered as the natural generalization of the well-known variational form of the nuclear norm to the nonconvex case i.e., for $p\in(0,1)$. Notably, low-rankness is now imposed via a group-sparsity promoting regularizer. The resulting formulation gives way to SVD-free algorithms thus offering lower computational complexity than the one that is induced by the original definition of the Schatten-$p$ quasi-norm. A local optimality analysis is provided which shows~that we can arrive at a local minimum of the original Schatten-$p$ quasi-norm problem by reaching a local minimum of the matrix factorization based surrogate problem. In addition, for the case of the squared Frobenious loss with linear operators obeying the restricted isometry property (RIP), a rank-one update scheme is proposed, which offers a way to escape poor local minima. Finally, the efficiency of our approach is empirically shown on a matrix completion problem.

The letter deals with the problem known as robust principal component analysis (RPCA), that is, the decomposition of a data matrix as the sum of a low-rank matrix component and a sparse matrix component. After expressing the low-rank matrix component in factorized form, we develop a novel online RPCA algorithm that is based entirely on reweighted least squares recursions and is appropriate for sequential data processing. The proposed algorithm is fast, memory optimal and, as corroborated by indicative empirical results on simulated data and a video processing application, competitive to the state-of-the-art in terms of estimation performance.

Nonnegative matrix factorization (NMF) has attracted considerable attention over the past few years as is met in many modern machine learning applications. NMF presents some inherent challenges when it comes both to its theoretical understanding and the task of devising efficient algorithmic tools. In this paper, we deal with an issue that is inherent in NMF, i.e., the a priori unawareness of the true nonnegative rank. To this end, a novel constrained NMF formulation is proposed. The main premise of the new formulation is to first assume an overestimate of the rank and then reduce it by imposing column sparsity jointly on the nonnegative matrix factors using proper penalization. Borrowing ideas from the block successive upper bound minimization framework, an alternating minimization strategy is followed, while inexact projected Newton-type updates are used in order to guarantee the descent direction of the cost function at each iteration. The effectiveness of the proposed approach is verified on simulated data and a real music signal decomposition experiment.

Nowadays, many modern imaging applications generate large-scale and high-dimensional data. In order to efficiently handle these data, statistical tools amenable to exploiting their intrisic low-dimensional nature are needed. PCA is a ubiquitous method which has been widely applied in a variety of applications. However a major shortcoming of PCA is its sensitivity to gross errors - outliers. In light of this, robust PCA has been recently proposed. Robust PCA accounts for gross errors by assuming that the data matrix is the superposition of a low-rank matrix and a sparse matrix. In this work, a matrix factorization-based formulation of robust PCA which can efficiently handle large scale data is proposed. Low-rankness is imposed via a novel low-rank promoting term applied on the matrix factors, which can be viewed as a weighted version of the variational form of the nuclear norm. The newly formulated robust PCA problem is addressed via an alternating iteratively reweighted least squares-type algorithm. Simulated and real data experiments verify the effectiveness of the proposed algorithm as compared to other state-of-the-art robust PCA algorithms.

We introduce a tensor completion algorithm that uses a group-sparse regularizer with respect to the PARAFAC factors and is based on an optimization scheme that alternatingly minimizes a quadratic upper bound of the associated cost function. The proposed scheme allows matrixwise updates of the PARAFAC factors and, thus, leads to an efficient and scalable iterative algorithm, suitable for big-data applications. Experiments conducted on both synthetic and real data, corroborate the superior performance, in terms of runtime, of the proposed algorithm as compared with the other state-of-the-art approaches.

In a plethora of applications dealing with inverse problems, e.g., image processing, social networks, compressive sensing, and biological data processing, the signal of interest is known to be structured in several ways at the same time. This premise has recently guided research into the innovative and meaningful idea of imposing multiple constraints on the unknown parameters involved in the problem under study. For instance, when dealing with problems whose unknown parameters form sparse and low-rank matrices, the adoption of suitably combined constraints imposing sparsity and low rankness is expected to yield substantially enhanced estimation results. In this paper, we address the spectral unmixing problem in hyperspectral images. Specifically, two novel unmixing algorithms are introduced in an attempt to exploit both spatial correlation and sparse representation of pixels lying in the homogeneous regions of hyperspectral images. To this end, a novel mixed penalty term is first defined consisting of the sum of the weighted ℓ1and the weighted nuclear norm of the abundance matrix corresponding to a small area of the image determined by a sliding square window. This penalty term is then used to regularize a conventional quadratic cost function and impose simultaneous sparsity and low rankness on the abundance matrix. The resulting regularized cost function is minimized by: 1) an incremental proximal sparse and low-rank unmixing algorithm; and 2) an algorithm based on the alternating direction method of multipliers. The effectiveness of the proposed algorithms is illustrated in experiments conducted both on simulated and real data.