We study the minimization problem of a non-convex sparsity promoting penalty func- tion, the transformed l1 (TL1), and its application in compressed sensing (CS). The TL1 penalty inter- polates l0 and l1 norms through a nonnegative parameter a ∈ (0, +∞), similar to lp with p ∈ (0, 1], and is known to satisfy unbiasedness, sparsity and Lipschitz continuity properties. We first consider the constrained minimization problem, and discuss the exact recovery of l0 norm minimal solution based on the null space property (NSP). We then prove the stable recovery of l0 norm minimal solution if the sensing matrix A satisfies a restricted isometry property (RIP). We formulated a normalized problem to overcome the lack of scaling property of the TL1 penalty function. For a general sensing matrix A, we show that the support set of a local minimizer corresponds to linearly independent columns of A. Next, we present difference of convex algorithms for TL1 (DCATL1) in computing TL1-regularized con- strained and unconstrained problems in CS. The DCATL1 algorithm involves outer and inner loops of iterations, one time matrix inversion, repeated shrinkage operations and matrix-vector multiplications. The inner loop concerns an l1 minimization problem on which we employ the Alternating Direction Method of Multipliers (ADMM). For the unconstrained problem, we prove convergence of DCATL1 to a stationary point satisfying the first order optimality condition. In numerical experiments, we identify the optimal value a = 1, and compare DCATL1 with other CS algorithms on two classes of sensing ma- trices: Gaussian random matrices and over-sampled discrete cosine transform matrices (DCT). Among existing algorithms, the iterated reweighted least squares method based on l1/2 norm is the best in sparse recovery for Gaussian matrices, and the DCA algorithm based on l1 minus l2 penalty is the best for over-sampled DCT matrices. We find that for both classes of sensing matrices, the performance of DCATL1 algorithm (initiated with l1 minimization) always ranks near the top (if not the top), and is the most robust choice insensitive to the conditioning of the sensing matrix A. DCATL1 is also com- petitive in comparison with DCA on other non-convex penalty functions commonly used in statistics with two hyperparameters.

In this paper, we consider the harmonic extension problem, which is widely used in many applications of machine learning. We formulate the harmonic extension as solving a Laplace-Beltrami equation with Dirichlet boundary condition. We use the point integral method (PIM) to solve the Laplace-Beltrami equation. The basic idea of the PIM method is to approximate the Laplace equation using an integral equation, which is easy to be discretized from points. Based on the integral equation, we found that traditional graph Laplacian method (GLM) may fail to approximate the harmonic functions in the classical sense. For the Laplace-Beltrami equation with Dirichlet boundary, we can prove the convergence of the point integral method. The point integral method is also very easy to implement, which only requires a minor modification of the graph Laplacian. One important application of the harmonic extension in machine learning is semi-supervised learning. We run a popular semi-supervised learning algorithm by Zhu et al. over a couple of well-known datasets and compare the performance of the aforementioned approaches. Our experiments show the PIM performs the best. We also apply PIM to an image recovery problem and show it outperforms GLM. Finally, on a model problem of Laplace-Beltrami equation with Dirichlet boundary, we prove the convergence of the point integral method.

We explain how the classical notions of Fisher information of a random variable and Fisher information matrix of a random vector can be extended to a much broader setting. We also show that Stam’s inequality for Fisher information and Shannon entropy, as well as the more generalized versions proved earlier by the authors, are all special cases of more general sharp inequalities satisfied by random vectors. The extremal random vectors, which we call generalized Gaussians, contain Gaussians as a limiting case but are noteworthy because they are heavy- tailed.

The p-th moment matrix is defined for a real random vector, generalizing the classical covariance matrix. Sharp inequalities relating the p-th moment and Renyi entropy are established, generalizing the classical inequality relating the second moment and the Shannon entropy. The extremal distributions for these inequalities are completely characterized.

In this paper, we show that every $(2^{n-1}+1)$-vertex induced subgraph of the $n$-dimensional cube graph has maximum degree at least $\sqrt{n}$. This result is best possible, and improves a logarithmic lower bound shown by Chung, F\"uredi, Graham and Seymour in 1988. As a direct consequence, we prove that the sensitivity and degree of a boolean function are polynomially related, solving an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.