Hyperspectral sensors measure the radiance spectrum across hundreds of wavelength channels with a resolution typically on the order of 10 nm represented by the full-width-half-maximum (FWHM). The spectra are used in the study of surface materials in the biological, geological and oceanographic sciences to name a few, utilizing quantitative spectroscopic techniques. The instruments developed to measure such data are expensive due to the increased number of bands, and create large datasets that can be difficult to downlink for a given instance. Repeat cycle of space-borne hyperspectral observations of the earth surface is also less than those of multi-spectral sensors. It becomes incumbent to develop mechanisms that could be cost-effective and give desired results. With this aim, spectral Super-Resolution (SR) is attempted on the Airborne Visible and Infra-Red Imaging Spectrometer (AVIRIS) data to reconstruct the hyperspectral band radiance from equally-spaced narrow multi-spectral bands using dictionary learning, followed by denoising using machine learning. The hyperspectral band radiance are first estimated from 30 selected input multi-spectral bands using dictionary trained through K-Singular Value Decomposition (K-SVD), followed by denoising using Random Forest Regression. An overall Signal-to-Noise Ratio (SNR) of 31.58dB is observed from reconstruction after denoising using Random Forest.

Tensor train decomposition is widely used in machine learning and quantum physics due to its concise representation of high-dimensional tensors, overcoming the curse of dimensionality. Cross approximation---originally developed for representing a matrix from a set of selected rows and columns---is an efficient method for constructing a tensor train decomposition of a tensor from few of its entries. While tensor train cross approximation has achieved remarkable performance in practical applications, its theoretical analysis, in particular regarding the error of the approximation, is so far lacking. To our knowledge, existing results only provide element-wise approximation accuracy guarantees, which lead to a very loose bound when extended to the entire tensor. In this paper, we bridge this gap by providing accuracy guarantees in terms of the entire tensor for both exact and noisy measurements. Our results illustrate how the choice of selected subtensors affects the quality of the cross approximation and that the approximation error caused by model error and/or measurement error may not grow exponentially with the order of the tensor. These results are verified by numerical experiments, and may have important implications for the usefulness of cross approximations for high-order tensors, such as those encountered in the description of quantum many-body states.

Estimating a sparse signal from its low-dimensional observations arises in many applications including signal demixing and compression. If each dictionary atom undergoes an unknown modulation process, this problem becomes a sparse recovery and blind demodulation problem. In this paper, we further allow the modulation process to be different for different dictionary atoms, which is known as non-stationary modulation. In the presence of noise, the sparse signal and modulation parameters cannot be recovered exactly. We propose to solve the support recovery problem with non-stationary modulation via an optimization-inspired data-driven method. Specifically, by assuming the modulating signals live in a known common subspace and applying the lifting technique, we formulate the support recovery problem as recovering a column-wise sparse matrix from linear observations, which could then be solved via a block $\ell_{1}$ norm regularized quadratic minimization. By unfolding the proximal gradient descent algorithm for that regularized quadratic minimization and replacing the proximal operator with a proximal network, we construct a novel recurrent neural network (RNN) to efficiently solve the support recovery problem. Experiments indicate that the proposed network is very efficient in solving the support recovery problem, can be adaptive to different sensing processes without retraining the network, and is applicable when the matrix of interest is not strictly column-wise sparse and when we only know an approximation of the sensing process.

This paper considers general rank-constrained optimization problems that minimize a general objective function${f}( {X})$over the set of rectangular${n}\times {m}$matrices that have rank at most r. To tackle the rank constraint and also to reduce the computational burden, we factorize$ {X}$into$ {U} {V} ^{\mathrm {T}}$where$ {U}$and$ {V}$are${n}\times {r}$and${m}\times {r}$matrices, respectively, and then optimize over the small matrices$ {U}$and$ {V}$. We characterize the global optimization geometry of the nonconvex factored problem and show that the corresponding objective function satisfies the robust strict saddle property as long as the original objective function f satisfies restricted strong convexity and smoothness properties, ensuring global convergence of many local search algorithms (such as noisy gradient descent) in polynomial time for solving the factored problem. We also provide a comprehensive analysis for the optimization geometry of a matrix factorization problem where we aim to find${n}\times {r}$and${m}\times {r}$matrices$ {U}$and$ {V}$such that$ {U} {V} ^{\mathrm {T}}$approximates a given matrix$ {X}^\star $. Aside from the robust strict saddle property, we show that the objective function of the matrix factorization problem has no spurious local minima and obeys the strict saddle property not only for the exact-parameterization case where$\mathrm {rank}( {X}^\star) = {r}$, but also for the over-parameterization case where$\mathrm {rank}( {X}^\star) < {r}$and the under-parameterization case where$\mathrm {rank}( {X}^\star) > {r}$. These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) converge to a global solution with random initialization.

Given a set of 3D to 2D putative matches, labeling the correspondences as inliers or outliers plays a critical role in a wide range of computer vision applications including the Perspective-n-Point (PnP) and object recognition. In this paper, we study a more generalized problem which allows the matches to belong to multiple objects with distinct poses. We propose a deep architecture to simultaneously label the correspondences as inliers or outliers and classify the inliers into multiple objects. Specifically, we discretize the 3D rotation space into twenty convex cones based on the facets of a regular icosahedron. For each facet, a facet classifier is trained to predict the probability of a correspondence being an inlier for a pose whose rotation normal vector points towards this facet. An efficient RANSAC-based post-processing algorithm is also proposed to further process the prediction results and detect the objects. Experiments demonstrate that our method is very efficient compared to existing methods and is capable of simultaneously labeling and classifying the inliers of multiple objects with high precision.

Low-rank matrix recovery is a fundamental problem in signal processing and machine learning. A recent very popular approach to recovering a low-rank matrix X is to factorize it as a product of two smaller matrices, i.e., X = UVT, and then optimize over U, V instead of X. Despite the resulting non-convexity, recent results have shown that many factorized objective functions actually have benign global geometry-with no spurious local minima and satisfying the so-called strict saddle property-ensuring convergence to a global minimum for many local-search algorithms. Such results hold whenever the original objective function is restricted strongly convex and smooth. However, most of these results actually consider a modified cost function that includes a balancing regularizer. While useful for deriving theory, this balancing regularizer does not appear to be necessary in practice. In this work, we close this theory-practice gap by proving that the unaltered factorized non-convex problem, without the balancing regularizer, also has similar benign global geometry. Moreover, we also extend our theoretical results to the field of distributed optimization.

Non-stationary blind super-resolution is an extension of the traditional super-resolution problem, which deals with the problem of recovering fine details from coarse measurements. The non-stationary blind super-resolution problem appears in many applications including radar imaging, 3D single-molecule microscopy, computational photography, etc. There is a growing interest in solving non-stationary blind super-resolution task with convex methods due to their robustness to noise and strong theoretical guarantees. Motivated by the recent work on atomic norm minimization in blind inverse problems, we focus here on the signal denoising problem in non-stationary blind super-resolution. In particular, we use an atomic norm regularized least-squares problem to denoise a sum of complex exponentials with unknown waveform modulations. We quantify how the mean square error depends on the noise variance and the true signal parameters. Numerical experiments are also implemented to illustrate the theoretical result.

Blind deconvolution and phase retrieval are both fundamental problems with a growing interest in signal processing and communications. In this work, we consider the task of simultaneous blind deconvolution and phase retrieval. We show that this non-linear problem can be reformulated as a low-rank tensor recovery problem and propose an algorithm named TIHT-BDPR to recover the unknown parameters. We include a series of numerical simulations to illustrate the effectiveness of our proposed algorithm.

A variety of unconstrained nonconvex optimization problems have been shown to have benign geometric landscapes that satisfy the strict saddle property and have no spurious local minima. We present a general result relating the geometry of an unconstrained centralized problem to its equality-constrained distributed extension. It follows that many global consensus problems inherit the benign geometry of their original centralized counterpart. Taking advantage of this fact, we demonstrate the favorable performance of the Gradient ADMM algorithm on a distributed low-rank matrix approximation problem.

In this paper, we consider a general sparse recovery and blind demodulation model. Different from the ones in the literature, in our general model, each dictionary atom undergoes a distinct modulation process; we refer to this as non-stationary modulation. We also assume that the modulation matrices live in a known subspace. Through the lifting technique, the sparse recovery and blind demodulation problem can be reformulated as a column-wise sparse matrix recovery problem, and we are able to recover both the sparse source signal and a cluster of modulation matrices via atomic norm and the induced `2,1norm minimizations. Moreover, we show that the sampling complexity for exact recovery is proportional to the number of degrees of freedom up to log factors in the noiseless case. We also bound the recovery error in terms of the norm of the noise when the observation is noisy. Numerical simulations are conducted to illustrate our results.

Non-negative sparse recovery refers to recovering non-negative sparse source signals from linear observations. This model arises naturally in many image processing applications such as super-resolution and image inpainting. In this paper, we propose two efficient neural networks for fast approximation of non-negative sparse recovery. We also derive upper bounds on network sizes measured by the numbers of layers and neurons to achieve a specified approximation error. Numerical experiments demonstrate the effectiveness and robustness of the proposed networks and show their potential in solving more complicated signal recovery problems with non-stationary transformation process and noisy observation.

This work studies the second-order convergence for both standard alternating minimization and proximal alternating minimization. We show that under mild assumptions on the (nonconvex) objective function, both algorithms avoid strict saddles almost surely from random initialization. Together with known first-order convergence results, this implies both algorithms converge to a second-order stationary point. This solves an open problem for the second-order convergence of alternating minimization algorithms that have been widely used in practice to solve large-scale nonconvex problems due to their simple implementation, fast convergence, and superb empirical performance.

The landscape of empirical risk has been widely studied in a series of machine learning problems, including low-rank matrix factorization, matrix sensing, matrix completion, and phase retrieval. In this work, we focus on the situation where the corresponding population risk is a degenerate non-convex loss function, namely, the Hessian of the population risk can have zero eigenvalues. Instead of analyzing the non-convex empirical risk directly, we first study the landscape of the corresponding population risk, which is usually easier to characterize, and then build a connection between the landscape of the empirical risk and its population risk. In particular, we establish a correspondence between the critical points of the empirical risk and its population risk without the strongly Morse assumption, which is required in existing literature but not satisfied in degenerate scenarios. We also apply the theory to matrix sensing and phase retrieval to demonstrate how to infer the landscape of empirical risk from that of the corresponding population risk.

Low-rank matrix factorization is a problem of broad importance, owing to the ubiquity of low-rank models in machine learning contexts. In spite of its non- convexity, this problem has a well-behaved geometric landscape, permitting local search algorithms such as gradient descent to converge to global minimizers. In this paper, we study low-rank matrix factorization in the distributed setting, where local variables at each node encode parts of the overall matrix factors, and consensus is encouraged among certain such variables. We identify conditions under which this new problem also has a well-behaved geometric landscape, and we propose an extension of distributed gradient descent (DGD) to solve this problem. The favorable landscape allows us to prove convergence to global optimality with exact consensus, a stronger result than what is provided by off-the-shelf DGD theory.

Principal Component Analysis (PCA) is one of the most broadly used methods to analyze high-dimensional data. However, most existing studies on PCA aim to minimize the reconstruction error measured by the Euclidean distance, although in some fields, such as text analysis in information retrieval, analysis using the angle distance is known to be more effective. In this paper, we propose a novel PCA formulation by adding a constraint on the factors to unify the Euclidean distance and the angle distance. Because the objective and constraints are nonconvex, the optimization problem is difficult to solve in general. To tackle the optimization problem, we propose an alternating linearized minimization method with guaranteed convergence and provable convergence rate. Experiments on synthetic data and real-world data sets have validated the effectiveness of our new method and demonstrated its advantages over state-of-art competing methods.

Recognizing three dimensional chess pieces using computer vision is needed for an augmented reality chess assistant. This paper proposes an efficient 3D pieces recognition approach based on oriented chamfer matching. During a real game, the pieces might be occluded by other pieces and have varying rotation and scales with respect to the camera. Furthermore, different pieces share lots of similar texture features which makes them more difficult to identify. Our approach addresses the above problems and is capable of identifying the pieces with different scales, rotation and viewing angles. After marking the possible chessboard squares that contain pieces, the oriented chamfer scores are calculated for alternative templates and the recognized pieces are indicated on the input image accordingly. Our approach shows high recognition accuracy and efficiency in experiments and the recognition process can be easily generalized to other pattern recognition applications with 3D templates. Our approach outperforms the convolutional neural networks under severe occlusion and low resolution conditions and has comparative processing time while avoids the time consuming training process.

Chessboards are commonly used to calibrate cameras, and many robust methods have been developed to recognize the unoccupied boards. However, when the chessboard is populated with chess pieces, such as during an actual game, the problem of recognizing the board is much harder. Challenges include occlusion caused by the chess pieces, the presence of outlier lines and low viewing angles of the chessboard. In this paper, we present a novel approach to address the above challenges and recognize the chessboard. The Canny edge detector and Hough transform are used to capture all possible lines in the scene. The k-means clustering and a k-nearest-neighbors inspired algorithm are applied to cluster and reject the outlier lines based on their Euclidean distances to the nearest neighbors in a scaled Hough transform space. Finally, based on prior knowledge of the chessboard structure, a geometric constraint is used to find the correspondences between image lines and the lines on the chessboard through the homography transformation. The proposed algorithm works for a wide range of the operating angles and achieves high accuracy in experiments.

In this paper, we propose a new framework for parameter estimation of complex exponentials from their modulations with unknown waveforms via convex programming. Our model generalizes the recently developed blind sparse spike deconvolution framework by Y. Chi [1] to the non-stationary scenario and encompasses a wide spectrum of applications. Under the assumption that the unknown waveforms live in a common random subspace, we recast the problem into an atomic norm minimization framework by a lifting trick, and this problem can be solved using computationally efficient semidefinite programming. We show that the number of measurements for exact recovery is proportional to the number of degrees of freedom in the problem, up to polylogarithmic factors. Numerical experiments support our theoretical findings.

Super-resolution is generally referred to as the task of recovering fine details from coarse information. Motivated by applications, such as single-molecule imaging, radar imaging, etc., we consider parameter estimation of complex exponentials from their modulations with unknown waveforms, allowing for non-stationary blind super-resolution. This problem, however, is ill-posed since both the parameters associated with the complex exponentials and the modulating waveforms are unknown. To alleviate this, we assume that the unknown waveforms live in a common low-dimensional subspace. Using a lifting trick, we recast the blind super-resolution problem as a structured low-rank matrix recovery problem. Atomic norm minimization is then used to enforce the structured low-rankness, and is reformulated as a semidefinite program that is solvable in polynomial time. We show that, up to scaling ambiguities, exact recovery of both of the complex exponential parameters and the unknown waveforms is possible when the waveform subspace is random and the number of measurements is proportional to the number of degrees of freedom in the problem. Numerical simulations support our theoretical findings, showing that non-stationary blind super-resolution using atomic norm minimization is possible.

We develop a theoretical and computational framework to perform guaranteed tensor decomposition, which also has the potential to accomplish other tensor tasks such as tensor completion and denoising. We formulate tensor decomposition as a problem of measure estimation from moments. By constructing a dual polynomial, we demonstrate that measure optimization returns the correct CP decomposition under an incoherence condition on the rank-one factors. To address the computational challenge, we present a hierarchy of semidefinite programs based on sums-of-squares relaxations of the measure optimization problem. By showing that the constructed dual polynomial is a sum-of-squares modulo the sphere, we prove that the smallest SDP in the relaxation hierarchy is exact and the decomposition can be extracted from the solution under the same incoherence condition. One implication is that the tensor nuclear norm can be computed exactly using the smallest SDP as long as the rank-one factors of the tensor are incoherent. Numerical experiments are conducted to test the performance of the moment approach.

Motivated by the problem of robust factorization of a low-rank tensor, we study the question of sparse and low-rank tensor decomposition. We present an efficient computational algorithm that modifies Leurgans' algoirthm for tensor factorization. Our method relies on a reduction of the problem to sparse and low-rank matrix decomposition via the notion of tensor contraction. We use well-understood convex techniques for solving the reduced matrix sub-problem which then allows us to perform the full decomposition of the tensor. We delineate situations where the problem is recoverable and provide theoretical guarantees for our algorithm. We validate our algorithm with numerical experiments.

This paper establishes a nearly optimal algorithm for denoising a mixture of sinusoids from noisy equispaced samples. We derive our algorithm by viewing line spectral estimation as a sparse recovery problem with a continuous, infinite dictionary. We show how to compute the estimator via semidefinite programming and provide guarantees on its mean-squared error rate. We derive a complementary minimax lower bound on this estimation rate, demonstrating that our approach nearly achieves the best possible estimation error. Furthermore, we establish bounds on how well our estimator localizes the frequencies in the signal, showing that the localization error tends to zero as the number of samples grows. We verify our theoretical results in an array of numerical experiments, demonstrating that the semidefinite programming approach outperforms three classical spectral estimation techniques.

This paper studies the sample complexity of searching over multiple populations. We consider a large number of populations, each corresponding to either distribution P0or P1. The goal of the search problem studied here is to find one population corresponding to distribution P1with as few samples as possible. The main contribution is to quantify the number of samples needed to correctly find one such population. We consider two general approaches: nonadaptive sampling methods, which sample each population a predetermined number of times until a population following P1is found, and adaptive sampling methods, which employ sequential sampling schemes for each population. We first derive a lower bound on the number of samples required by any sampling scheme. We then consider an adaptive procedure consisting of a series of sequential probability ratio tests, and show it comes within a constant factor of the lower bound. We give explicit expressions for this constant when samples of the populations follow Gaussian and Bernoulli distributions. An alternative adaptive scheme is discussed which does not require full knowledge of P1, and comes within a constant factor of the optimal scheme. For comparison, a lower bound on the sampling requirements of any nonadaptive scheme is presented.

This paper investigates the problem of estimating the frequency components of a mixture of s complex sinusoids from a random subset of n regularly spaced samples. Unlike previous work in compressed sensing, the frequencies are not assumed to lie on a grid, but can assume any values in the normalized frequency domain [0, 1]. An atomic norm minimization approach is proposed to exactly recover the unobserved samples and identify the unknown frequencies, which is then reformulated as an exact semidefinite program. Even with this continuous dictionary, it is shown that O(slog s log n) random samples are sufficient to guarantee exact frequency localization with high probability, provided the frequencies are well separated. Extensive numerical experiments are performed to illustrate the effectiveness of the proposed method.

Typical user demands of electricity vary throughout the day, which increases the cost to utility companies and decreases the stability of the power system. Time-of-use (TOU) pricing has been proposed as a demand-side management (DSM) method to influence user demands. In this paper, we describe a new approach of optimal TOU pricing strategy based on game theory (GT-TOU). We propose models for costs due to the fluctuating user demands to the utility companies, as well as the user satisfaction measurement because of the difference between the demand and actual load. We design utility functions for the company and the user, and obtain the Nash equilibrium using backward induction and iterative methods. Numerical example shows that our method is effective in leveling the user demand by setting optimal TOU prices, in potentially increasing the profit of the utility companies and ensuring overall user benefit.

The stability of low-rank matrix reconstruction with respect to noise is investigated in this paper. The$\ell _{\ast}$-constrained minimal singular value ($\ell _{\ast}$-CMSV) of the measurement operator is shown to determine the recovery performance of nuclear norm minimization-based algorithms. Compared with the stability results using the matrix restricted isometry constant, the performance bounds established using$\ell _{\ast}$-CMSV are more concise, and their derivations are less complex. Isotropic and subgaussian measurement operators are shown to have$\ell _{\ast}$-CMSVs bounded away from zero with high probability, as long as the number of measurements is relatively large. The$\ell _{\ast}$-CMSV for correlated Gaussian operators are also analyzed and used to illustrate the advantage of$\ell _{\ast}$-CMSV compared with the matrix restricted isometry constant. We also provide a fixed point characterization of$\ell _{\ast}$-CMSV that is potentially useful for its computation.

We analyze the performance of a direction-of-arrival (DOA) estimation scheme based on overcomplete signal representation in this paper. We formulate the problem as a support recovery problem with joint sparsity constraints and analyze it in a hypothesis testing framework. We derive both upper and lower bounds on the probability of error by using Chernoff bound and Fano's inequality, respectively. The lower bound implies that the minimal number of samples necessary for accurate DOA estimation is proportional to the logarithm of the discretization level for arbitrary isotropic sensor arrays. We apply the upper bound to study the effect of noise. For uniform linear array (ULA) with only one source, the upper bound exponent indicates that the optimal overcomplete representation is achieved by uniform partition of the wave number space instead of the DOA space.

The performance of estimating the common support for jointly sparse signals based on their projections onto lower-dimensional space is analyzed. Support recovery is formulated as a multiple-hypothesis testing problem. Both upper and lower bounds on the probability of error are derived for general measurement matrices, by using the Chernoff bound and Fano's inequality, respectively. The upper bound shows that the performance is determined by a quantity measuring the measurement matrix incoherence, while the lower bound reveals the importance of the total measurement gain. The lower bound is applied to derive the minimal number of samples needed for accurate direction-of-arrival (DOA) estimation for a sparse representation based algorithm. When applied to Gaussian measurement ensembles, these bounds give necessary and sufficient conditions for a vanishing probability of error for majority realizations of the measurement matrix. Our results offer surprising insights into sparse signal recovery. For example, as far as support recovery is concerned, the well-known bound in Compressive Sensing with the Gaussian measurement matrix is generally not sufficient unless the noise level is low. Our study provides an alternative performance measure, one that is natural and important in practice, for signal recovery in Compressive Sensing and other application areas exploiting signal sparsity.