Abstract. Many inverse problems and signal processing problems involve low-rank regularizers based on the nuclear norm. Commonly, proximal gradient methods (PGMs) are adopted to solve this type of nonsmooth problems, as they can offer fast and guaranteed convergence. However, PGM methods cannot be simply applied in settings where low-rank models are imposed locally on overlapping patches; therefore, heuristic approaches have been proposed that lack convergence guarantees. In this work we propose to replace the nuclear norm with a smooth approximation in which a Huber-type function is applied to each singular value. By providing a theoretical framework based on singular value function theory, we show that important properties can be established for the proposed regularizer, such as convexity, differentiability, and Lipschitz continuity of the gradient. Moreover, we provide a closed-form expression for the regularizer gradient, enabling the use of standard iterative gradient-based optimization algorithms (e.g., the nonlinear conjugate gradient) that can easily address the case of overlapping patches and have well-known convergence guarantees. In addition, we provide a novel step-size selection strategy based on a quadratic majorizer of the line search function that leverages the Huber characteristics of the proposed regularizer. Finally, we assess the proposed optimization framework by providing empirical results in dynamic magnetic resonance imaging (MRI) reconstruction in the context of local low-rank models with overlapping patches.

This paper introduces a novel approach to robust surface reconstruction from photometric stereo normal vector maps that is particularly well-suited for reconstructing surfaces from noisy gradients. Specifically, we propose an adaptive dictionary learning based approach that attempts to simultaneously integrate the gradient fields while sparsely representing the spatial patches of the reconstructed surface in an adaptive dictionary domain. We show that our formulation learns the underlying structure of the surface, effectively acting as an adaptive regularizer that enforces a smoothness constraint on the reconstructed surface. Our method is general and may be coupled with many existing approaches in the literature to improve the integrity of the reconstructed surfaces. We demonstrate the performance of our method on synthetic data as well as real photometric stereo data and evaluate its robustness to noise.

Photometric stereo is a method for estimating the normal vectors of an object from images of the object under varying lighting conditions. Motivated by several recent works that extend photometric stereo to more general objects and lighting conditions, we study a new robust approach to photometric stereo that utilizes dictionary learning. Specifically, we propose and analyze two approaches to adaptive dictionary regularization for the photometric stereo problem. First, we propose an image preprocessing step that utilizes an adaptive dictionary learning model to remove noise and other non-idealities from the image dataset before estimating the normal vectors. We also propose an alternative model where we directly apply the adaptive dictionary regularization to the normal vectors themselves during estimation. We study the practical performance of both methods through extensive simulations, which demonstrate the state-of-the-art performance of both methods in the presence of noise.

We consider two matrix-valued data sets that are modeled as low-rank-correlated-signal-plus-Gaussian noise. When empirical canonical correlation analysis (CCA) is used to infer these latent correlations, there is a broad regime, where this inference will fail, which was classified by Bao and collaborators in the limit of high dimensionality and sample size. This regime includes the setting, previously considered by Pezeshki and collaborators, where the sample size is less than the combined dimensionality of the data sets. We revisit this detection problem by first observing that the empirically estimated canonical correlation coefficients are the singular values of the inner products between the right singular vectors of the two data sets. Motivated by random matrix theory insights, we propose an algorithm, which we label informative CCA (ICCA), that infers the presence of latent correlations by considering the singular values of only the informative right singular vectors of each data set. We establish fundamental detection limits for ICCA and show that it dramatically outperforms empirical CCA in broad regimes, where empirical CCA provably fails. We extend our theoretical analysis to the setting, where the data sets have randomly missing data and for more general noise models. Finally, we validate our theoretical results with numerical simulations and a real-world experiment.

Sparsity-based approaches have been popular in many applications in image processing and imaging. Compressed sensing exploits the sparsity of images in a transform domain or dictionary to improve image recovery fromundersampledmeasurements. In the context of inverse problems in dynamic imaging, recent research has demonstrated the promise of sparsity and low-rank techniques. For example, the patches of the underlying data are modeled as sparse in an adaptive dictionary domain, and the resulting image and dictionary estimation from undersampled measurements is called dictionary-blind compressed sensing, or the dynamic image sequence is modeled as a sum of low-rank and sparse (in some transform domain) components (L+S model) that are estimated from limited measurements. In this work, we investigate a data-adaptive extension of the L+S model, dubbed LASSI, where the temporal image sequence is decomposed into a low-rank component and a component whose spatiotemporal (3D) patches are sparse in some adaptive dictionary domain. We investigate various formulations and efficient methods for jointly estimating the underlying dynamic signal components and the spatiotemporal dictionary from limited measurements. We also obtain efficient sparsity penalized dictionary-blind compressed sensing methods as special cases of our LASSI approaches. Our numerical experiments demonstrate the promising performance of LASSI schemes for dynamicmagnetic resonance image reconstruction from limited k-t space data compared to recent methods such as k-t SLR and L+S, and compared to the proposed dictionary-blind compressed sensing method.

Traditional passive radar systems with a noisy reference signal use the cross-correlation statistic for detection. However, owing to the composite nature of this hypothesis testing problem, no claims can be made about the optimality of this detector. In this paper, we consider digital illuminators such that the transmitted signal in a processing interval is a weighted periodic summation of several identical pulses. The target reflectivity is assumed to change independently from one pulse to another within a processing interval. Inspired by random matrix theory, we propose a singular value decomposition (SVD) and Eigen detector for this model that significantly outperforms the conventional cross-correlation detector. We demonstrate this performance improvement through extensive numerical simulations across various surveillance and reference signal-to-noise ratio (SNR) regimes.

We consider the problem of estimating the singular vectors of low-rank signal matrices buried in noise in the setting where the singular vectors are assumed to be Kronecker products of unknown vectors. We propose four algorithms for estimating such singular vectors, analyze their performance and show that they asymptotically fail to estimate to latent singular vector below the same critical SNR. We corroborate our theoretical findings with numerical simulations and illustrate the improved performance on a STAP beamforming application.

The truncated singular value decomposition of the measurement matrix is the optimal solution to the representation problem of how to best approximate a noisy measurement matrix using a low-rank matrix. Here, we consider the (unobservable) denoising problem of how to best approximate a low-rank signal matrix buried in noise by optimal (re)weighting of the singular vectors of the measurement matrix. We exploit recent results from random matrix theory to exactly characterize the large matrix limit of the optimal weighting coefficients and show that they can be computed directly from data for a large class of noise models that includes the independent identically distributed Gaussian noise case. Our analysis brings into sharp focus the shrinkage-and-thresholding form of the optimal weights, the nonconvex nature of the associated shrinkage function (on the singular values), and explains why matrix regularization via singular value thresholding with convex penalty functions (such as the nuclear norm) will always be suboptimal. We validate our theoretical predictions with numerical simulations, develop an implementable algorithm (OptShrink) that realizes the predicted performance gains and show how our methods can be used to improve estimation in the setting where the measured matrix has missing entries.

Past improvements in clock frequencies have traditionally been obtained through technology scaling, but most recent technology nodes do not offer such benefits. Instead, parallelism has emerged as the key driver of chip-performance growth. Unfortunately, efficient simultaneous use of on-chip resources is hampered by sequential dependencies, as illustrated by Amdahl's law. Quantifying achievable parallelism in terms of provable mathematical results can help prevent futile programming efforts and guide innovation in computer architecture toward the most significant challenges. To complement Amdahl's law, we focus on stream processing and quantify performance losses due to stochastic runtimes. Using spectral theory of random matrices, we derive new analytical results and validate them by numerical simulations. These results allow us to explore unique benefits of stochasticity and show how and when they outweigh the costs for software streams.

With the end of clock-frequency scaling, parallelism has emerged as the key driver of chip-performance growth. Yet, several factors undermine efficient simultaneous use of on-chip resources, which continue scaling with Moore's law. These factors are often due to sequential dependencies, as illustrated by Amdahl's law.

The MVDR beamformer is the most extensively used array processing algorithm and involves inverting the sample covariance matrix. In the snapshot deficient scenario, when the number of sensors is greater than or approximately equal to the number of snapshots, the eigenvalues of the resulting sample covariance matrix are poorly conditioned. Diagonal loading is then applied to the sample covariance matrix. Expressions for the bias of the resulting MVDR beamformer outputs in the sidelobe region are presented that are exact for asymptotically large arrays. Numerical simulations confirm the accuracy of these asymptotic expressions when predicting the bias of the outputs of moderately large arrays.