We propose a variational tail bound for norms of random vectors and matrices under moment assumptions on their one-dimensional marginals. A simplified version of the bound that parametrizes the “aggregating distribution” using a certain pushforward of the Gaussian distribution is also provided. We apply the proposed method to reproduce some of the well-known bounds on norms of Gaussian random vectors, and also obtain dimension-free tail bounds for the Euclidean norm of random vectors with arbitrary moment profiles. Furthermore, we reproduce a dimension-free concentration inequality for sum of independent and identically distributed positive semidefinite matrices with sub-exponential marginals, and obtain a concentration inequality for the sample covariance matrix of sub-exponential random vectors. We also obtain a tail bound for the operator norm of a random matrix series whose random coefficients may have arbitrary moment profiles. Furthermore, we use coupling to formulate an abstraction of the proposed approach that applies more broadly. As a corollary, we derive a PAC-Bayesian-style bound in terms of a certain combination of the KL and Rényi divergences between the prior and posterior distributions.

We formulate a uniform tail bound for empirical processes indexed by a class of functions, in terms of the individual deviations of the functions rather than the worst-case deviation in the considered class. The tail bound is established by introducing an initial “deflation” step to the standard generic chaining argument. The resulting tail bound is the sum of the complexity of the “deflated function class” in terms of a generalization of Talagrand’s γ functional, and the deviation of the function instance, both of which are formulated based on the natural seminorm induced by the corresponding Cramér functions. Leveraging another less demanding natural seminorm, we also show similar bounds, though with implicit dependence on the sample size, in the more general case where finite exponential moments cannot be assumed. We also provide approximations of the tail bounds in terms of the more prevalent Orlicz norms or their “incomplete” versions under suitable moment conditions.

We consider the multivariate max-linear regression problem where the model parameters$ {\beta }_{1},\dotsc, {\beta }_{k}\in \mathbb {R}^{p}$need to be estimated from$n$independent samples of the (noisy) observations$y = \max _{1\leq j \leq k} {\beta }_{j}^{\mathsf {T}} {x} + \mathrm {noise}$. The max-linear model vastly generalizes the conventional linear model, and it can approximate any convex function to an arbitrary accuracy when the number of linear models$k$is large enough. However, the inherent nonlinearity of the max-linear model renders the estimation of the regression parameters computationally challenging. Particularly, no estimator based on convex programming is known in the literature. We formulate and analyze a scalable convex program given by anchored regression (AR) as the estimator for the max-linear regression problem. Under the standard Gaussian observation setting, we present a non-asymptotic performance guarantee showing that the convex program recovers the parameters with high probability. When the$k$linear components are equally likely to achieve the maximum, our result shows a sufficient number of noise-free observations for exact recovery scales as$k^{4}p$up to a logarithmic factor. This sample complexity coincides with that by alternating minimization (Ghosh et al., 2021). Moreover, the same sample complexity applies when the observations are corrupted with arbitrary deterministic noise. We provide empirical results that show that our method performs as our theoretical result predicts, and is competitive with the alternating minimization algorithm particularly in presence of multiplicative Bernoulli noise. Furthermore, we also show empirically that a recursive application of AR can significantly improve the estimation accuracy.

We propose a flexible convex relaxation for the phase retrieval problem that operates in the natural domain of the signal. Therefore, we avoid the prohibitive computational cost associated with “lifting” and semidefinite programming (SDP) in methods such as PhaseLift and compete with recently developed non-convex techniques for phase retrieval. We relax the quadratic equations for phaseless measurements to inequality constraints each of which representing a symmetric “slab”. Through a simple convex program, our proposed estimator finds an extreme point of the intersection of these slabs that is best aligned with a given anchor vector. We characterize geometric conditions that certify success of the proposed estimator. Furthermore, using classic results in statistical learning theory, we show that for random measurements the geometric certificates hold with high probability at an optimal sample complexity. Phase transition of our estimator is evaluated through simulations. Our numerical experiments also suggest that the proposed method can solve phase retrieval problems with coded diffraction measurements as well.

Several convex formulation methods have been proposed previously for statistical estimation with structured sparsity as the prior. These methods often require a carefully tuned regularization parameter, often a cumbersome or heuristic exercise. Furthermore, the estimate that these methods produce might not belong to the desired sparsity model, albeit accurately approximating the true parameter. Therefore, greedy-type algorithms could often be more desirable in estimating structured-sparse parameters. So far, these greedy methods have mostly focused on linear statistical models. In this paper, we study the projected gradient descent with a non-convex structured-sparse parameter model as the constraint set. Should the cost function have a stable model-restricted Hessian, the algorithm produces an approximation for the desired minimizer. As an example, we elaborate on application of the main results to estimation in generalized linear models.

We propose a robust and efficient approach to the problem of compressive phase retrieval in which the goal is to reconstruct a sparse vector from the magnitude of a number of its linear measurements. The proposed framework relies on constrained sensing vectors and a two-stage reconstruction method that consists of two standard convex programs that are solved sequentially.In recent years, various methods are proposed for compressive phase retrieval, but they have suboptimal sample complexity or lack robustness guarantees. The main obstacle has been that there is no straightforward convex relaxations for the type of structure in the target. Given a set of underdetermined measurements, there is a standard framework for recovering a sparse matrix, and a standard framework for recovering a low-rank matrix. However, a general, efficient method for recovering a jointly sparse and low-rank matrix has remained elusive.Deviating from the models with generic measurements, in this paper we show that if the sensing vectors are chosen at random from an incoherent subspace, then the low-rank and sparse structures of the target signal can be effectively decoupled. We show that a recovery algorithm that consists of a low-rank recovery stage followed by a sparse recovery stage will produce an accurate estimate of the target when the number of measurements is $\mathsf{O}(k\,\log\frac{d}{k})$, where $k$ and $d$ denote the sparsity level and the dimension of the input signal. We also evaluate the algorithm through numerical simulation.

In this paper we analyze the blind deconvolution of an image and an unknown blur in a coded imaging system. The measurements consist of subsampled convolution of an unknown blurring kernel with multiple random binary modulations (coded masks) of the image. To perform the deconvolution, we consider a standard lifting of the image and the blurring kernel that transforms the measurements into a set of linear equations of the matrix formed by their outer product. Any rank-one solution to this system of equations provides a valid pair of an image and a blur. We first express the necessary and sufficient conditions for the uniqueness of a rank-one solution under some additional assumptions (uniform subsampling and no limit on the number of coded masks). These conditions are a special case of a previously established result regarding identifiability in the matrix completion problem. We also characterize a low-dimensional subspace model for the blur kernel that is sufficient to guarantee identifiability, including the interesting instance of “bandpass” blur kernels. Next, assuming the bandpass model for the blur kernel, we show that the image and the blur kernel can be found using nuclear norm minimization. Our main results show that recovery is achieved (with high probability) when the number of masks is on the order of $\mu\log^{2}L\,\log\frac{Le}{\mu}\,\log\log(N+1),$ where $\mu$ is the coherence of the blur, $L$ is the dimension of the image, and $N$ is the number of measured samples per mask.

In this paper we present joint decoding of JPEG2000 bitstreams and Reed-Solomon codes in the context of unequal loss protection. Using error resilience features of JPEG2000 bitstreams, the joint decoder helps to restore the erased symbols when the Reed-Solomon decoder fails to retrieve them on its own. However, the joint decoding process might become time-consuming due to a search through the set of possible erased symbols. We propose the use of smaller codeblocks and transmission of a relatively small amount of side information with high reliability as two approaches to accelerate the joint decoding process. The accelerated joint decoder can deliver essentially the same quality enhancement as the nonaccelerated one, while operating several times faster.

In this paper we present improvements to the recently-proposed joint decoding of JPEG2000 bitstreams and Reed-Solomon codes in the context of unequal loss protection. Using error resilience features of JPEG2000 bitstreams, the joint decoder helps to restore the erased symbols when the Reed-Solomon decoder fails to retrieve them on its own. We make use of the ability of the JPEG2000 decoder to provide rough error localization within a coding pass to speed up the search for erased symbol values. In addition, we show how transmitting a relatively small amount of side information with high reliability may help the joint decoder by reducing the size of the search space and bypassing some of the JPEG2000 decoding iterations needed to verify the correctness of the restored source information. The improved joint decoder is up to 20 times faster compared to the previous one.

This paper presents a method for joint decoding of JPEG2000 bistreams and Reed-Solomon codes in the context of unequal loss protection. When the Reed-Solomon decoder is unable to retrieve the erased source symbols, the proposed joint decoder searches through the set of possible erased source symbols, making use of error resilience features of JPEG2000 to retrieve correct symbols. The joint decoder can be used as an add-on module to some of the existing schemes for unequal loss protection, and can improve the PSNR of decoded images by over 10 dB in some cases.