Matrix recovery is raised in many areas. In this paper, we build up a framework for almost everywhere matrix recovery which means to recover almost all the @math from @math where @math . We mainly focus on the following question: how many measurements are needed to recover almost all the matrices in @math ? For the case where both @math and @math are algebraic varieties, we use the tools from algebraic geometry to study the question and present some results to address it under many different settings.
In applications throughout science and engineering one is often faced with the challenge of solving an ill-posed inverse problem, where the number of available measurements is smaller than the dimension of the model to be estimated. However in many practical situations of interest, models are constrained structurally so that they only have a few degrees of freedom relative to their ambient dimension. This paper provides a general framework to convert notions of simplicity into convex penalty functions, resulting in convex optimization solutions to linear, underdetermined inverse problems. The class of simple models considered includes those formed as the sum of a few atoms from some (possibly infinite) elementary atomic set; examples include well-studied cases from many technical fields such as sparse vectors (signal processing, statistics) and low-rank matrices (control, statistics), as well as several others including sums of a few permutation matrices (ranked elections, multiobject tracking), low-rank tensors (computer vision, neuroscience), orthogonal matrices (machine learning), and atomic measures (system identification). The convex programming formulation is based on minimizing the norm induced by the convex hull of the atomic set; this norm is referred to as the atomic norm. The facial structure of the atomic norm ball carries a number of favorable properties that are useful for recovering simple models, and an analysis of the underlying convex geometry provides sharp estimates of the number of generic measurements required for exact and robust recovery of models from partial information. These estimates are based on computing the Gaussian widths of tangent cones to the atomic norm ball. When the atomic set has algebraic structure the resulting optimization problems can be solved or approximated via semidefinite programming. The quality of these approximations affects the number of measurements required for recovery, and this tradeoff is characterized via some examples. Thus this work extends the catalog of simple models (beyond sparse vectors and low-rank matrices) that can be recovered from limited linear information via tractable convex programming. Abstract The paper presents several results that address a fundamental question in low-rank matrix recovery: how many measurements are needed to recover low-rank matrices? We begin by investigating the complex matrices case and show that 4 n r − 4 r 2 generic measurements are both necessary and sufficient for the recovery of rank-r matrices in C n × n . Thus, we confirm a conjecture which is raised by Eldar, Needell and Plan for the complex case. We next consider the real case and prove that the bound 4 n r − 4 r 2 is tight provided n = 2 k + r , k ∈ Z + . Motivated by Vinzant's work [19] , we construct 11 matrices in R 4 × 4 by computer random search and prove they define injective measurements on rank-1 matrices in R 4 × 4 . This disproves the conjecture raised by Eldar, Needell and Plan for the real case. Finally, we use the results in this paper to investigate the phase retrieval by projection and show fewer than 2 n − 1 orthogonal projections are possible for the recovery of x ∈ R n from the norm of them, which gives a negative answer for a question raised in [1] .  Abstract Low-rank matrix recovery addresses the problem of recovering an unknown low-rank matrix from few linear measurements. There has been a large influx of literature deriving conditions under which certain tractable methods will succeed in recovery, demonstrating that m ⩾ C n r Gaussian measurements are often sufficient to recover any rank-r n × n matrix. In this paper we address the theoretical question of how many measurements are needed via any method whatsoever — tractable or not. We show that for a family of random measurement ensembles, m ⩾ 4 n r − 4 r 2 and m ⩾ 2 n r − r 2 + 1 measurements are sufficient to guarantee strong recovery and weak recovery, respectively, by rank minimization. These results give a benchmark to which we may compare the efficacy of tractable methods such as nuclear-norm minimization. This paper establishes information-theoretic limits for estimating a finite-field low-rank matrix given random linear measurements of it. These linear measurements are obtained by taking inner products of the low-rank matrix with random sensing matrices. Necessary and sufficient conditions on the number of measurements required are provided. It is shown that these conditions are sharp and the minimum-rank decoder is asymptotically optimal. The reliability function of this decoder is also derived by appealing to de Caen's lower bound on the probability of a union. The sufficient condition also holds when the sensing matrices are sparse-a scenario that may be amenable to efficient decoding. More precisely, it is shown that if the n × n-sensing matrices contain, on average, Ω(nlog n) entries, the number of measurements required is the same as that when the sensing matrices are dense and contain entries drawn uniformly at random from the field. Analogies are drawn between the aforementioned results and rank-metric codes in the coding theory literature. In fact, we are also strongly motivated by understanding when minimum rank distance decoding of random rank-metric codes succeeds. To this end, we derive minimum distance properties of equiprobable and sparse rank-metric codes. These distance properties provide a precise geometric interpretation of the fact that the sparse ensemble requires as few measurements as the dense one.