Recent works on adaptive sparse and on low-rank signal modeling have demonstrated their usefulness in various image/video processing applications. Patch-based methods exploit local patch sparsity, whereas other works apply low-rankness of grouped patches to exploit image non-local structures. However, using either approach alone usually limits performance in image reconstruction or recovery applications. In this work, we propose a simultaneous sparsity and low-rank model, dubbed STROLLR, to better represent natural images. In order to fully utilize both the local and non-local image properties, we develop an image restoration framework using a transform learning scheme with joint low-rank regularization. The approach owes some of its computational efficiency and good performance to the use of transform learning for adaptive sparse representation rather than the popular synthesis dictionary learning algorithms, which involve approximation of NP-hard sparse coding and expensive learning steps. We demonstrate the proposed framework in various applications to image denoising, inpainting, and compressed sensing based magnetic resonance imaging. Results show promising performance compared to state-of-the-art competing methods.

Multichannel blind deconvolution is the problem of recovering an unknown signal f and multiple unknown channels xifrom convolutional measurements yi= xi⊕ f (i = 1, 2, ..., N). We consider the case where the xi's are sparse, and convolution with f is invertible. Our nonconvex optimization formulation solves for a filter h on the unit sphere that produces sparse output yi⊕ h. Under some technical assumptions, we show that all local minima of the objective function correspond to the inverse filter of f up to an inherent sign and shift ambiguity, and all saddle points have strictly negative curvatures. This geometric structure allows successful recovery of f and xiusing a simple manifold gradient descent algorithm with random initialization. Our theoretical findings are complemented by numerical experiments, which demonstrate superior performance of the proposed approach over the previous methods.

Multichannel blind deconvolution is the problem of recovering an unknown signal f and multiple unknown channels xifrom their circular convolution yi= xi® f (i = 1, 2, . .., N). We consider the case where the xi's are sparse, and convolution with f is invertible. Our nonconvex optimization formulation solves for a filter h on the unit sphere that produces sparse output yi® h. Under some technical assumptions, we show that all local minima of the objective function correspond to the inverse filter of f up to an inherent sign and shift ambiguity, and all saddle points have strictly negative curvatures. This geometric structure allows successful recovery of f and xiusing a simple manifold gradient descent (MGD) algorithm. The same approach is also applicable to blind gain and phase calibration with a Fourier sensing matrix. Our algorithm and analysis require fewer assumptions than previous algorithms for the same problem. Our theoretical findings are complemented by numerical experiments, which demonstrate superior performance of the proposed approach over the previous methods. Empirically, our algorithm has low computation cost (converging in a small number of iterations) and low memory footprint (solving only for the inverse filter of f ).

Blind gain and phase calibration (BGPC) is a bilinear inverse problem involving the determination of unknown gains and phases of the sensing system, and the unknown signal, jointly. BGPC arises in numerous applications, e.g., blind albedo estimation in inverse rendering, synthetic aperture radar autofocus, and sensor array auto-calibration. In some cases, sparse structure in the unknown signal alleviates the ill-posedness of BGPC. Recently, there has been renewed interest in solutions to BGPC with careful analysis of error bounds. In this paper, we formulate BGPC as an eigenvalue/eigenvector problem and propose to solve it via power iteration, or in the sparsity or joint sparsity case, via truncated power iteration. Under certain assumptions, the unknown gains, phases, and the unknown signal can be recovered simultaneously. Numerical experiments show that power iteration algorithms work not only in the regime predicted by our main results, but also in regimes where theoretical analysis is limited. We also show that our power iteration algorithms for BGPC compare favorably with competing algorithms in adversarial conditions, e.g., with noisy measurement or with a bad initial estimate.

Multichannel blind deconvolution is the problem of recovering an unknown signal $f$ and multiple unknown channels $x_i$ from convolutional measurements $y_i=x_i \circledast f$ ($i=1,2,\dots,N$). We consider the case where the $x_i$'s are sparse, and convolution with $f$ is invertible. Our nonconvex optimization formulation solves for a filter $h$ on the unit sphere that produces sparse output $y_i\circledast h$. Under some technical assumptions, we show that all local minima of the objective function correspond to the inverse filter of $f$ up to an inherent sign and shift ambiguity, and all saddle points have strictly negative curvatures. This geometric structure allows successful recovery of $f$ and $x_i$ using a simple manifold gradient descent algorithm with random initialization. Our theoretical findings are complemented by numerical experiments, which demonstrate superior performance of the proposed approach over the previous methods.

Compressed sensing is provided a data-acquisition paradigm for sparse signals. Remarkably, it has been shown that the practical algorithms provide robust recovery from noisy linear measurements acquired at a near optimal sampling rate. In many real-world applications, a signal of interest is typically sparse not in the canonical basis but in a certain transform domain, such as wavelets or the finite difference. The theory of compressed sensing was extended to the analysis sparsity model, but known extensions are limited to the specific choices of sensing matrix and sparsifying transform. In this paper, we propose a unified theory for robust recovery of sparse signals in a general transform domain by convex programming. In particular, our results apply to the general acquisition and sparsity models and show how the number of measurements for recovery depends on properties of measurement and sparsifying transforms. Moreover, we also provide extensions of our results to the scenarios where the atoms in the transform have varying incoherence parameters and the unknown signal exhibits a structured sparsity pattern. In particular, for the partial Fourier recovery of sparse signals over a circulant transform, our main results suggest a uniformly random sampling. Numerical results demonstrate that the variable density random sampling by our main results provides a superior recovery performance over the known sampling strategies.

Recent works on adaptive sparse signal modeling have demonstrated their usefulness in various image/video processing applications. As the popular synthesis dictionary learning methods involve NP-hard sparse coding and expensive learning steps, transform learning has recently received more interest for its cheap computation. However, exploiting local patch sparsity alone usually limits performance in various image processing tasks. In this work, we propose a joint adaptive patch sparse and group low-rank model, dubbed STROLLR, to better represent natural images. We develop an image restoration framework based on the proposed model, which involves a simple and efficient alternating algorithm. We demonstrate applications, including image denoising and inpainting. Results show promising performance even when compared to state-of-the-art methods.

Recent works on adaptive sparse and low-rank signal modeling have demonstrated their usefulness, especially in image/video processing applications. While a patch-based sparse model imposes local structure, low-rankness of the grouped patches exploits non-local correlation. Applying either approach alone usually limits performance in various low-level vision tasks. In this work, we propose a novel video denoising method, based on an online tensor reconstruction scheme with a joint adaptive sparse and low-rank model, dubbed SALT. An efficient and unsupervised online unitary sparsifying transform learning method is introduced to impose adaptive sparsity on the fly. We develop an efficient 3D spatio-temporal data reconstruction framework based on the proposed online learning method, which exhibits low latency and can potentially handle streaming videos. To the best of our knowledge, this is the first work that combines adaptive sparsity and low-rankness for video denoising, and the first work of solving the proposed problem in an online fashion. We demonstrate video denoising results over commonly used videos from public datasets. Numerical experiments show that the proposed video denoising method outperforms competing methods.

Subsampled blind deconvolution is the recovery of two unknown signals from samples of their convolution. To overcome the ill-posedness of this problem, solutions based on priors tailored to specific practical application have been developed. In particular, sparsity models have provided promising priors. However, in spite of the empirical success of these methods in many applications, existing analyses are rather limited in two main ways: by disparity between the theoretical assumptions on the signal and/or measurement model versus practical setups; or by failure to provide a performance guarantee for parameter values within the optimal regime defined by the information theoretic limits. In particular, it has been shown that a naive sparsity model is not a strong enough prior for identifiability in the blind deconvolution problem. Instead, in addition to sparsity, we adopt a conic constraint, which enforces spectral flatness of the signals. Under this prior together with random dictionary models, we show that the unknown sparse signals can be recovered from samples of their convolution at a rate scaling near optimally with the problem parameters. We also propose an iterative algorithm that is guaranteed to provide robust recovery at the same near optimal sample complexity provided that certain projection steps in the algorithm are successful. In our analysis, we have not verified the success of these projection steps, but these steps are inactive with high probability. Numerical results show the empirical performance of the iterative algorithm agrees with the performance guarantee.

Bilinear inverse problems (BIPs), the resolution of two vectors given their image under a bilinear mapping, arise in many applications. Without further constraints, BIPs are usually ill-posed. In practice, the properties of natural signals are exploited to solve BIPs. For example, subspace constraints or sparsity constraints are imposed to reduce the search space. These approaches have shown some success in practice. However, there are few results on uniqueness in BIPs. For most BIPs, the fundamental question of under what condition the problem admits a unique solution is yet to be answered. For example, blind gain and phase calibration (BGPC) is a structured BIP, which arises in many applications, including inverse rendering in computational relighting (albedo estimation with unknown lighting), blind phase and gain calibration in sensor array processing, and multichannel blind deconvolution (MBD). It is interesting to study the uniqueness of such problems. In this paper, we define identifiability of a BIP up to a group of transformations. We derive necessary and sufficient conditions for such identifiability, i.e., the conditions under which the solutions can be uniquely determined up to the transformation group. These conditions take the form of dividing the identifiability of the pair of unknown variables into the individual identifiability of each variable. Although verifying these individual conditions requires problem-specific procedures, this framework is universally applicable to all BIPs. Applying these results to BGPC, we derive sufficient conditions for unique recovery under several scenarios, including subspace, joint sparsity, and sparsity models. For BGPC with joint sparsity or sparsity constraints, we develop a procedure to compute the transformation groups corresponding to inherent ambiguities. We also give necessary conditions in the form of tight lower bounds on sample complexities, and demonstrate the tightness of these bounds by numerical experiments. The results for BGPC not only demonstrate the application of the proposed general framework for identifiability analysis, but are also of interest in their own right.

Blind deconvolution (BD) arises in many applications. Without assumptions on the signal and the filter, BD does not admit a unique solution. In practice, subspace or sparsity assumptions have shown the ability to reduce the search space and yield the unique solution. However, existing theoretical analysis on uniqueness in BD is rather limited. In an earlier paper, we provided the first algebraic sample complexities for BD that hold for Lebesgue almost all bases or frames. We showed that for BD of a pair of vectors in ℂn, with subspace constraints of dimensions m1and m2, respectively, a sample complexity of n ≥ m1m2is sufficient. This result is suboptimal, since the number of degrees of freedom is merely m1+ m2- 1. We provided analogous results, with similar suboptimality, for BD with sparsity or mixed subspace and sparsity constraints. In this paper, taking advantage of the recent progress on the information-theoretic limits of unique low-rank matrix recovery, we finally bridge this gap, and derive an optimal sample complexity result for BD with generic bases or frames. We show that for BD of an arbitrary pair (respectively, all pairs) of vectors in ℂn, with sparsity constraints of sparsity levels s1 and s2, a sample complexity of n > s1+ s2[respectively, n > 2(s1+s2)] is sufficient. We also present analogous results for BD with subspace constraints or mixed constraints, with the subspace dimension replacing the sparsity level. Last but not least, in all the above scenarios, if the bases or frames follow a probabilistic distribution specified in this paper, the recovery is not only unique, but also stable against small perturbations in the measurements, under the same sample complexities.

Tremendous efforts have been made to study the theoretical and algorithmic aspects of sparse recovery and low-rank matrix recovery. This paper establishes (near) optimal sample complexities for stable matrix recovery without constants or log factors. We treat sparsity, low-rankness, and other parsimonious structures within the same framework: constraint sets that have small covering numbers or Minkowski dimensions, which include notoriously challenging cases such as simultaneously sparse and low-rank matrices. We consider three types of random measurement matrices (unstructured, rank-1, and symmetric rank-1 matrices), following probability distributions that satisfy some mild conditions. In all these cases, we prove a fundamental achievability result - the recovery of matrices with parsimonious structures, using an optimal (or near optimal) number of measurements, is stable with high probability.

Blind deconvolution (BD), the resolution of a signal and a filter given their convolution, arises in many applications. Without further constraints, BD is ill-posed. In practice, subspace or sparsity constraints have been imposed to reduce the search space, and have shown some empirical success. However, the existing theoretical analysis on uniqueness in BD is rather limited. In an effort to address the still open question, we derive sufficient conditions under which two vectors can be uniquely identified from their circular convolution, subject to subspace or sparsity constraints. These sufficient conditions provide the first algebraic sample complexities for BD. We first derive a sufficient condition that applies to almost all bases or frames. For BD of vectors in ℂn, with two subspace constraints of dimensions m1and m2, the required sample complexity is n ≥ m1m2. Then, we impose a sub-band structure on one basis, and derive a sufficient condition that involves a relaxed sample complexity n≥ m1+m2-1, which we show to be optimal. We present the extensions of these results to BD with sparsity constraints or mixed constraints, with the sparsity level replacing the subspace dimension. The cost for the unknown support in this case is an extra factor of 2 in the sample complexity.