We address the problem of minimizing a convex function over the space of large matrices with low rank. While this optimization problem is hard in general, we propose an efficient greedy algorithm and derive its formal approximation guarantees. Each iteration of the algorithm involves (approximately) finding the left and right singular vectors corresponding to the largest singular value of a certain matrix, which can be calculated in linear time. This leads to an algorithm which can scale to large matrices arising in several applications such as matrix completion for collaborative filtering and robust low rank matrix approximation.
As mentioned earlier, the problem defined in has many applications, and therefore it was studied in various contexts. A popular approach is to use the trace norm as a surrogate for the rank (e.g. @cite_20 ). This approach is closely related to the idea of using the @math norm as a surrogate for sparsity, because low rank corresponds to sparsity of the vector of singular values and the trace norm is the @math norm of the vector of singular values. This approach has been extensively studied, mainly in the context of collaborating filtering. See for example @cite_27 @cite_12 @cite_6 @cite_1 @cite_21 .
@cite_21 @cite_1 @cite_6 @cite_27 @cite_20 @cite_12
2950602671 2127300249 2128007683 2094394132
Using the @math -norm to regularize the estimation of the parameter vector of a linear model leads to an unstable estimator when covariates are highly correlated. In this paper, we introduce a new penalty function which takes into account the correlation of the design matrix to stabilize the estimation. This norm, called the trace Lasso, uses the trace norm, which is a convex surrogate of the rank, of the selected covariates as the criterion of model complexity. We analyze the properties of our norm, describe an optimization algorithm based on reweighted least-squares, and illustrate the behavior of this norm on synthetic data, showing that it is more adapted to strong correlations than competing methods such as the elastic net. The problem of consistently estimating the sparsity pattern of a vector β* ∈ RP based on observations contaminated by noise arises in various contexts, including signal denoising, sparse approximation, compressed sensing, and model selection. We analyze the behavior of l1-constrained quadratic programming (QP), also referred to as the Lasso, for recovering the sparsity pattern. Our main result is to establish precise conditions on the problern dimension p, the number k of nonzero elements in β*, and the number of observations n that are necessary and sufficient for sparsity pattern recovery using the Lasso. We first analyze the case of observations made using deterministic design matrices and sub-Gaussian additive noise, and provide sufficient conditions for support recovery and l∞-error bounds, as well as results showing the necessity of incoherence and bounds on the minimum value. We then turn to the case of random designs, in which each row of the design is drawn from a N(0, Σ) ensemble. For a broad class of Gaussian ensembles satisfying mutual incoherence conditions, we compute explicit values of thresholds 0 0, if n > 2(θu + δ)k log(p - k), then the Lasso succeeds in recovering the sparsity pattern with probability converging to one for large problems, whereas for n < 2(θl - δ)k log(p - k), then the probability of successful recovery converges to zero. For the special case of the uniform Gaussian ensemble (Σ = I p×p), we show that θl = θu = 1, so that the precise threshold n = 2k log (p - k) is exactly determined. It has been known for a while that l1-norm relaxation can in certain cases solve an under-determined system of linear equations. Recently, E. Candes ("Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information," IEEE Trans. Information Theory, vol. 52, no. 12, pp. 489-509, Dec. 2006) and D. Donoho ("High-dimensional centrally symmetric polytopes with neighborlines proportional to dimension," Disc. Comput. Geometry, vol. 35, no. 4, pp. 617-652, 2006) proved (in a large dimensional and statistical context) that if the number of equations (measurements in the compressed sensing terminology) in the system is proportional to the length of the unknown vector then there is a sparsity (number of nonzero elements of the unknown vector) also proportional to the length of the unknown vector such that l1-norm relaxation succeeds in solving the system. In this paper, in a large dimensional and statistical context, we determine sharp lower bounds on the values of allowable sparsity for any given number (proportional to the length of the unknown vector) of equations for the case of the so-called block-sparse unknown vectors considered in "On the reconstruction of block-sparse signals with an optimal number of measurements," (M. , IEEE Trans, Signal Processing, submitted for publication. In geometric computer vision, the structure from motion (SfM) problem can be formulated as a optimization problem with a rank constraint. It is well known that the trace norm of a matrix can act as a convex proxy for a low rank constraint. Hence, in recent work [7], the trace-norm relaxation has been applied to the SfM problem. However, SfM problems often exhibit a certain structure, for example a smooth camera path. Unfortunately, the trace norm relaxation can not make use of this additional structure. This observation motivates the main contribution of this paper. We present the so-called generalized trace norm which allows to encode prior knowledge about a specific problem into a convex regularization term which enforces a low rank solution while at the same time taking the problem structure into account. While deriving the generalized trace norm and stating its different formulations, we draw interesting connections to other fields, most importantly to the field of compressive sensing. Even though the generalized trace norm is a very general concept with a wide area of potential applications we are ultimately interested in applying it to SfM problems. Therefore, we also present an efficient algorithm to optimize the resulting generalized trace norm regularized optimization problems. Results show that the generalized trace norm indeed achieves its goals in providing a problem-dependent regularization.