#### DMCA

## Low rank matrix recovery from rank one measurements (2014)

Citations: | 3 - 1 self |

### Citations

7417 | Convex Optimization
- Boyd, Vandenberghe
- 2004
(Show Context)
Citation Context ...ation corresponds to minimize Z∈Hn ‖Z‖1 subject to ‖A(Z)− b‖ℓ2 ≤ η. (4) This is a convex optimization problem which can be solved computationally efficiently with various strategies [33, Chapter 15], =-=[10, 23, 62, 71]-=-. We note that several alternatives to nuclear norm minimization may also be applied including iteratively reweighted least squares [32], iterative hard thresholding [47, 70], greedy approaches [51] a... |

3592 | Compressed sensing
- Donoho
- 2006
(Show Context)
Citation Context ...olarization identities [2] or alternate projections [60]. Yet another recent method is phase retrieval via Wirtinger flow [14]. 1.2. Low rank matrix recovery. Building on ideas of compressive sensing =-=[18, 27, 33]-=-, low rank matrix recovery aims to reconstruct a matrix of low rank from incomplete linear measurements via efficient algorithms [63]. For our purposes we concentrate on Hermitian matrices X ∈ Cn×n an... |

1497 | Near-optimal signal recovery from random projections: Universal encoding strategies
- Candès, Tao
- 2006
(Show Context)
Citation Context ...olarization identities [2] or alternate projections [60]. Yet another recent method is phase retrieval via Wirtinger flow [14]. 1.2. Low rank matrix recovery. Building on ideas of compressive sensing =-=[18, 27, 33]-=-, low rank matrix recovery aims to reconstruct a matrix of low rank from incomplete linear measurements via efficient algorithms [63]. For our purposes we concentrate on Hermitian matrices X ∈ Cn×n an... |

864 | Exact matrix completion via convex optimization
- Candes, Recht
- 2009
(Show Context)
Citation Context ...ctural assumption of low rank assures that the matrix is sparse in its eigenbasis. In parallel to the prominent role of ℓ1-norm minimization in compressive sensing [33], it is by now well-appreciated =-=[1, 17, 16, 63, 35]-=- that in many relevant measurement scenarios, the sought for matrix X can be efficiently recovered via convex programming, although the corresponding rank minimization problem is NP hard in general [2... |

794 |
Quantum Computation and Quantum Information (Cambridge
- Nielsen, Chuang
- 2001
(Show Context)
Citation Context ... Chapter 2.2.6] for further information. For practical reasons, it is highly desirable that a quantum measurement (represented by a POVM) can be implemented with reasonable effort. In accordance with =-=[61]-=-, we call a POVM-measurement efficient (or practical), if it can be carried out by performing a number of O (polylog(n)) elementary steps2. Making this notion precise would go beyond the scope of this... |

561 | Gaurateed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Recht, Fazel, et al.
- 2007
(Show Context)
Citation Context ... matrix recovery. Building on ideas of compressive sensing [18, 27, 33], low rank matrix recovery aims to reconstruct a matrix of low rank from incomplete linear measurements via efficient algorithms =-=[63]-=-. For our purposes we concentrate on Hermitian matrices X ∈ Cn×n and consider measurements of the form tr (XAj) = bj j = 1, . . . ,m (2) where the Aj ∈ Cn×n are some Hermitian matrices. For notational... |

349 | Introduction to the non-asymptotic analysis of random matrices - Vershynin - 2011 |

287 | Phase retrieval algorithms: A comparison
- Fienup
- 1982
(Show Context)
Citation Context ...s that the signal x enters the measurement process (1) quadratically. This leads to a non-linear inverse problem. Classical approaches to numerically solving it include alternating projection methods =-=[30, 34]-=-. However, these methods usually require extra constraints and careful selection of parameters, and in particular, no rigorous convergence or recovery guarantees seem to be available. As Balan et al. ... |

285 |
Matrix rank minimization with applications
- Fazel
- 2002
(Show Context)
Citation Context ...5] that in many relevant measurement scenarios, the sought for matrix X can be efficiently recovered via convex programming, although the corresponding rank minimization problem is NP hard in general =-=[28]-=-. In order to formulate this convex program, we introduce the standard ℓp-norm on R n or Cn by ‖x‖ℓp = ( ∑n ℓ=1 |xℓ|p)1/p for 1 ≤ p <∞ and the Schatten-p-norm on the space Hn of Hermitian n× n matrice... |

265 | Proximal splitting methods in signal processing
- Combettes, Pesquet
- 2011
(Show Context)
Citation Context ...ation corresponds to minimize Z∈Hn ‖Z‖1 subject to ‖A(Z)− b‖ℓ2 ≤ η. (4) This is a convex optimization problem which can be solved computationally efficiently with various strategies [33, Chapter 15], =-=[10, 23, 62, 71]-=-. We note that several alternatives to nuclear norm minimization may also be applied including iteratively reweighted least squares [32], iterative hard thresholding [47, 70], greedy approaches [51] a... |

250 | User-friendly tail bounds for sums of random matrices
- Tropp
- 2012
(Show Context)
Citation Context ...,Y ∈ Hn. (35) 5.2. Matrix Chernoff inequality. The matrix version of the classical Chernoff inequality for the expection of a sum of independent random matrices shown in [73, Theorem 5.1.1] (see also =-=[72]-=-) reads as follows. Theorem 15. Let X1, . . . , Xm be a sequence of independent random positive definite matrices in Hn satisfying ‖Xℓ‖∞ ≤ L almost surely for all ℓ = 1, . . . ,m. Then, for any τ > 0,... |

194 | Matrix completion from a few entries
- Keshavan, Montanari, et al.
- 2010
(Show Context)
Citation Context ...mization may also be applied including iteratively reweighted least squares [32], iterative hard thresholding [47, 70], greedy approaches [51] and algorithms specialized to certain measurement maps A =-=[43]-=-, but our analysis is geared towards nuclear norm minimization and does not provide guarantees for these other algorithms. Up to date, a number of measurement instances have been identified for which ... |

185 | Recovering low-rank matrices from few coefficients in any basis
- Gross
(Show Context)
Citation Context ...ctural assumption of low rank assures that the matrix is sparse in its eigenbasis. In parallel to the prominent role of ℓ1-norm minimization in compressive sensing [33], it is by now well-appreciated =-=[1, 17, 16, 63, 35]-=- that in many relevant measurement scenarios, the sought for matrix X can be efficiently recovered via convex programming, although the corresponding rank minimization problem is NP hard in general [2... |

183 | An accelerated proximal gradient algorithm for nuclear norm regular- ized least squares problems
- Toh, Yun
- 2009
(Show Context)
Citation Context ...ation corresponds to minimize Z∈Hn ‖Z‖1 subject to ‖A(Z)− b‖ℓ2 ≤ η. (4) This is a convex optimization problem which can be solved computationally efficiently with various strategies [33, Chapter 15], =-=[10, 23, 62, 71]-=-. We note that several alternatives to nuclear norm minimization may also be applied including iteratively reweighted least squares [32], iterative hard thresholding [47, 70], greedy approaches [51] a... |

182 | The convex geometry of linear inverse problems
- Chandrasekaran, Recht, et al.
- 2012
(Show Context)
Citation Context ...stances have been identified for which nuclear norm minimization (4) – and potentially other algorithms – provably recovers the sought for low-rank matrix from considerably fewer than n2 measurements =-=[17, 16, 20, 35, 32, 52, 63, 74]-=-. All these constructions are based on randomness, the simplest being a random Gaussian measurement map where all entries Aj,k,ℓ in the representation A(X)j = ∑n k,ℓ=1Aj,k,ℓXk,ℓ are independent mean z... |

153 | Enumerative Combinatorics, Volume I, - Stanley - 1986 |

103 |
Spherical codes and designs
- Delsarte, Goethals, et al.
- 1997
(Show Context)
Citation Context ...r result in a non-optimal sampling rate [38, 15, 37]. 1.3. Weighted complex projective designs. The concept of real spherical designs was introduced by Delsarte Goethals and Seidel in a seminal paper =-=[26]-=- and has been studied in algebraic combinatorics [68] and coding theory [26, 59]. Recently, complex projective designs – the natural extension of real spherical designs to the complex unit sphere – ha... |

90 |
Characterization of the subdifferential of some matrix norms, Linear Algebra and its Applications
- Watson
- 1992
(Show Context)
Citation Context ...t is well known that ∂‖X‖1 consists of all matrices of the form S = r∑ i=1 sgn(λi)xix ∗ i + S2, where S2 ∈ Hn has the property that S2xi = 0 for all i ∈ {1, . . . , r} and ‖S2‖∞ ≤ 1. (See for example =-=[78]-=-, where the real analogue is shown.) Consider now S = r∑ i=1 sgn(λi)xix ∗ i + τ −1A4 ∈ ∂‖X‖1, where τ = ‖A4‖∞. (If τ = 0, let S = ∑r i=1 sgn(λi)xix ∗ i .) To simplify the notation, write S1 = ∑r i=1 s... |

80 |
Quantum State Tomography via compressed sensing
- Gross, Lou, et al.
- 2009
(Show Context)
Citation Context ...ator has rank one and almost pure if it is well approximated by a matrix of low rank rank(ρ) = r ≪ n. Assuming this structural property, quantum state tomography is a low-rank matrix recovery problem =-=[39, 35, 31, 52]-=-. An additional requirement for tomography is the fact that the measurement process has to be “experimentally realizable” and – preferably – “efficiently” so. Any “experimentally realizable” quantum m... |

79 |
Tensors: geometry and applications
- Landsberg
- 2012
(Show Context)
Citation Context ...tilinear algebra. We briefly repeat some standard concepts in multilinear algebra which are convenient for our proof of Proposition 12. They can be found in any textbook on multilinear algebra – e.g. =-=[49]-=- – but we nonetheless include them here for the sake of being self-contained. Let V1, . . . , Vk be (finite dimensional, complex) vector spaces and let V ∗ 1 , . . . , V ∗ k denote their duals. A func... |

76 | Admira: Atomic decomposition for minimum rank approximation
- Lee, Bresler
- 2010
(Show Context)
Citation Context ...2, 71]. We note that several alternatives to nuclear norm minimization may also be applied including iteratively reweighted least squares [32], iterative hard thresholding [47, 70], greedy approaches =-=[51]-=- and algorithms specialized to certain measurement maps A [43], but our analysis is geared towards nuclear norm minimization and does not provide guarantees for these other algorithms. Up to date, a n... |

72 |
On signal reconstruction without phase
- Balan, Casazza, et al.
(Show Context)
Citation Context ... signal from measurements that are ignorant towards phases is abundant in many different areas of science, such as X-ray cristallography [40, 57], astronomy [29] diffraction imaging [67, 57] and more =-=[8, 12, 76]-=-. Mathematically formulated, the problem consists of recovering a complex signal (vector) x ∈ Cn from measurements of the form |〈aj , x〉|2 = bj for j = 1, . . . ,m, (1) where a1, . . . , am ∈ Cn are s... |

72 |
Phase retrieval in crystallography and optics
- Millane
- 1990
(Show Context)
Citation Context ...he phase retrieval problem. The problem of retrieving a complex signal from measurements that are ignorant towards phases is abundant in many different areas of science, such as X-ray cristallography =-=[40, 57]-=-, astronomy [29] diffraction imaging [67, 57] and more [8, 12, 76]. Mathematically formulated, the problem consists of recovering a complex signal (vector) x ∈ Cn from measurements of the form |〈aj , ... |

65 | Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
- Candès, Plan
(Show Context)
Citation Context ...ctural assumption of low rank assures that the matrix is sparse in its eigenbasis. In parallel to the prominent role of ℓ1-norm minimization in compressive sensing [33], it is by now well-appreciated =-=[1, 17, 16, 63, 35]-=- that in many relevant measurement scenarios, the sought for matrix X can be efficiently recovered via convex programming, although the corresponding rank minimization problem is NP hard in general [2... |

57 |
Quantendesigns. Grundzüge einer nichtkommutativen designtheorie
- Zauner
- 1999
(Show Context)
Citation Context ...g theory [26, 59]. Recently, complex projective designs – the natural extension of real spherical designs to the complex unit sphere – have been of considerable interest in quantum information theory =-=[79, 65, 41, 36, 53, 11, 48]-=-. Roughly speaking, a complex projective t-design is a finite subset of the complex unit sphere in Cn with the particular property that the discrete average of any polynomial of degree (t, t) (i.e., a... |

49 | Painless reconstruction from magnitudes of frame coefficients
- Balan, Bodmann, et al.
- 2009
(Show Context)
Citation Context ...e methods usually require extra constraints and careful selection of parameters, and in particular, no rigorous convergence or recovery guarantees seem to be available. As Balan et al. pointed out in =-=[7]-=-, this apparent obstacle of having nonlinear measurements can be overcome by noting that the measurement process – while quadratic in x – is linear in the outer product xx∗: |〈aj , x〉|2 = tr ( aja ∗ j... |

48 | Randomizing quantum states: Constructions and applications
- Hayden, Leung, et al.
- 2004
(Show Context)
Citation Context ...f∥∥∥∥∥ N∑ i=1 pi (wiw ∗ i ) ⊗t − ∫ CPn−1 (ww∗)⊗t dw ∥∥∥∥∥ p ≤ ( n+ t− 1 t )−1 θp. (10) While accuracy measured in arbitrary Schatten-p-norms is conceivable, the ones measured in operator norm (p = ∞) =-=[42, 3, 54, 11]-=- and nuclear norm (p = 1) [58] are the ones most commonly used – at least in quantum information theory. For these two accuracies, the definition in particular assures that every approximate t-design ... |

47 |
Fienup, "Phase Retrieval and Image Reconstruction for Astronomy
- Dainty, R
- 1987
(Show Context)
Citation Context ...roblem. The problem of retrieving a complex signal from measurements that are ignorant towards phases is abundant in many different areas of science, such as X-ray cristallography [40, 57], astronomy =-=[29]-=- diffraction imaging [67, 57] and more [8, 12, 76]. Mathematically formulated, the problem consists of recovering a complex signal (vector) x ∈ Cn from measurements of the form |〈aj , x〉|2 = bj for j ... |

38 |
Phase problem in crystallography
- Harrison
- 1993
(Show Context)
Citation Context ...he phase retrieval problem. The problem of retrieving a complex signal from measurements that are ignorant towards phases is abundant in many different areas of science, such as X-ray cristallography =-=[40, 57]-=-, astronomy [29] diffraction imaging [67, 57] and more [8, 12, 76]. Mathematically formulated, the problem consists of recovering a complex signal (vector) x ∈ Cn from measurements of the form |〈aj , ... |

38 |
Averaging sets: a generalization of mean values and spherical designs
- Seymour, Zaslavsky
- 1984
(Show Context)
Citation Context ...[55], we call a t-design proper, if all the weights are equal, i.e., pi = 1/N for all i = 1, . . . , N . Although exact, proper t-designs exist and can be constructed in any dimension n for any t ∈ N =-=[66, 6, 45, 41]-=-, these constructions are typically inefficient in the sense that they require vector sets of exponential size. For example, the construction in [41] requires on the order of O (t)n vectors which scal... |

34 |
The question of phase retrieval in optics
- Walther
- 1963
(Show Context)
Citation Context ... signal from measurements that are ignorant towards phases is abundant in many different areas of science, such as X-ray cristallography [40, 57], astronomy [29] diffraction imaging [67, 57] and more =-=[8, 12, 76]-=-. Mathematically formulated, the problem consists of recovering a complex signal (vector) x ∈ Cn from measurements of the form |〈aj , x〉|2 = bj for j = 1, . . . ,m, (1) where a1, . . . , am ∈ Cn are s... |

27 |
Diffractive imaging for periodic samples: retrieving one-dimensional concentration profiles across microfluidic channels. Acta Crystallographica Section A: Foundations of Crystallography
- Bunk, Diaz, et al.
(Show Context)
Citation Context ... signal from measurements that are ignorant towards phases is abundant in many different areas of science, such as X-ray cristallography [40, 57], astronomy [29] diffraction imaging [67, 57] and more =-=[8, 12, 76]-=-. Mathematically formulated, the problem consists of recovering a complex signal (vector) x ∈ Cn from measurements of the form |〈aj , x〉|2 = bj for j = 1, . . . ,m, (1) where a1, . . . , am ∈ Cn are s... |

27 |
A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis. Birkhäuser
- Foucart, Rauhut
- 2013
(Show Context)
Citation Context ...olarization identities [2] or alternate projections [60]. Yet another recent method is phase retrieval via Wirtinger flow [14]. 1.2. Low rank matrix recovery. Building on ideas of compressive sensing =-=[18, 27, 33]-=-, low rank matrix recovery aims to reconstruct a matrix of low rank from incomplete linear measurements via efficient algorithms [63]. For our purposes we concentrate on Hermitian matrices X ∈ Cn×n an... |

26 |
Tight informationally complete quantum measurements
- Scott
(Show Context)
Citation Context ...g theory [26, 59]. Recently, complex projective designs – the natural extension of real spherical designs to the complex unit sphere – have been of considerable interest in quantum information theory =-=[79, 65, 41, 36, 53, 11, 48]-=-. Roughly speaking, a complex projective t-design is a finite subset of the complex unit sphere in Cn with the particular property that the discrete average of any polynomial of degree (t, t) (i.e., a... |

24 |
The fourth moment method.
- Berger
- 1997
(Show Context)
Citation Context ... in [55]. However, since we are interested in a bound on the probability of an event happening, rather than bounding an expectation value, we use the Payley-Zygmund inequality instead of Berger’s one =-=[9]-=- (which states E [|S|] ≥ E [S2]3/2 E [S4]−1/2). Proof. The desired statement follows, if we can show that P (|tr (aa∗Z) | ≥ ξ) ≥ (1 − ξ 2)2 24 (24) holds for any matrix Z ∈ Hn obeying ‖Z‖2 = 1. For su... |

24 | Phase retrieval via wirtinger flow: theory and algorithms,”
- Candes, Li, et al.
- 2015
(Show Context)
Citation Context ...ery problem is just one possibility to retrieve phases. Other approaches use polarization identities [2] or alternate projections [60]. Yet another recent method is phase retrieval via Wirtinger flow =-=[14]-=-. 1.2. Low rank matrix recovery. Building on ideas of compressive sensing [18, 27, 33], low rank matrix recovery aims to reconstruct a matrix of low rank from incomplete linear measurements via effici... |

24 |
Bounding the smallest singular value of a random matrix without concentration. arXiv:1312.3580,
- Koltchinskii, Mendelson
- 2013
(Show Context)
Citation Context ...roofs Our proof technique consists in the application of a uniform version of Tropp’s bowling scheme, see [74]. The crucial ingredient is a new method due to Mendelson [56] and Koltchiskii, Mendelson =-=[44]-=- (see also [50]) to obtain lower bounds for quantities of the form infu∈E ∑m j=1 |〈φj , x〉|2 where the φj are independent random vectors in R d and E is a subset of Rd. We start by recalling from [74]... |

23 | Phase retrieval using alternating minimization
- Netrapalli, Jain, et al.
- 2013
(Show Context)
Citation Context ...ld be noted, however, that such a reduction to a low rank matrix recovery problem is just one possibility to retrieve phases. Other approaches use polarization identities [2] or alternate projections =-=[60]-=-. Yet another recent method is phase retrieval via Wirtinger flow [14]. 1.2. Low rank matrix recovery. Building on ideas of compressive sensing [18, 27, 33], low rank matrix recovery aims to reconstru... |

21 | Phase retrieval with polarization
- Alexeev, Bandeira, et al.
(Show Context)
Citation Context ... AND ULRICH TERSTIEGE It should be noted, however, that such a reduction to a low rank matrix recovery problem is just one possibility to retrieve phases. Other approaches use polarization identities =-=[2]-=- or alternate projections [60]. Yet another recent method is phase retrieval via Wirtinger flow [14]. 1.2. Low rank matrix recovery. Building on ideas of compressive sensing [18, 27, 33], low rank mat... |

21 |
Quantum tomography via compressed sensing: Error bounds, sample complexity, and efficient estimators,”
- Flammia, Gross, et al.
- 2012
(Show Context)
Citation Context ...ator has rank one and almost pure if it is well approximated by a matrix of low rank rank(ρ) = r ≪ n. Assuming this structural property, quantum state tomography is a low-rank matrix recovery problem =-=[39, 35, 31, 52]-=-. An additional requirement for tomography is the fact that the measurement process has to be “experimentally realizable” and – preferably – “efficiently” so. Any “experimentally realizable” quantum m... |

20 | Quantum t-designs: t-wise independence in the quantum world
- Ambainis, Emerson
(Show Context)
Citation Context ...igns as a general-purpose tool for de-randomization – see e.g. [38, Section 1.1.] for further reading on this topic. Also, Theorem 3 resembles insights in the context of distinguishing quantum states =-=[55, 3]-=-, where it was pointed out that (approximate) 4-designs “perform almost as good” as uniform measurements (projectors onto random Gaussian vectors). Note that we will generalize Theorem 3 to approximat... |

20 | Phase retrieval from coded diffraction patterns,” arXiv:1310.3240
- Candès, Li, et al.
- 2013
(Show Context)
Citation Context ...or) this obstacle could be overcome by providing problem specific recovery guarantees that either manifestly rely on (rank one) Gaussian measurements [13, 74] or result in a non-optimal sampling rate =-=[38, 15, 37]-=-. 1.3. Weighted complex projective designs. The concept of real spherical designs was introduced by Delsarte Goethals and Seidel in a seminal paper [26] and has been studied in algebraic combinatorics... |

20 |
Learning without concentration.
- Mendelson
- 2015
(Show Context)
Citation Context ...d of local random circuits. 4. Proofs Our proof technique consists in the application of a uniform version of Tropp’s bowling scheme, see [74]. The crucial ingredient is a new method due to Mendelson =-=[56]-=- and Koltchiskii, Mendelson [44] (see also [50]) to obtain lower bounds for quantities of the form infu∈E ∑m j=1 |〈φj , x〉|2 where the φj are independent random vectors in R d and E is a subset of Rd.... |

19 |
Cubature formulas, geometrical designs, reproducing kernels, and Markov operators
- Harpe, Pache
- 2005
(Show Context)
Citation Context ...toriously difficult to find. By introducing weights, it becomes simpler to obtain designs with a number of elements that scales polynomially in the dimension n. Some existence results can be found in =-=[25]-=-, where weighted t-designs appear under the notion of cubatures of strength t. It seems that one can construct weighted t-designs by drawing sufficiently many vectors at random and afterwards solving ... |

19 | Universal low-rank matrix recovery from Pauli measurements
- Liu
(Show Context)
Citation Context ...stances have been identified for which nuclear norm minimization (4) – and potentially other algorithms – provably recovers the sought for low-rank matrix from considerably fewer than n2 measurements =-=[17, 16, 20, 35, 32, 52, 63, 74]-=-. All these constructions are based on randomness, the simplest being a random Gaussian measurement map where all entries Aj,k,ℓ in the representation A(X)j = ∑n k,ℓ=1Aj,k,ℓXk,ℓ are independent mean z... |

18 | Blind deconvolution using convex programming. arXiv preprint arXiv:1211.5608
- Ahmed, Recht, et al.
- 2012
(Show Context)
Citation Context |

18 | Living on the edge: Phase transitions in convex programs with random data. - Amelunxen, McCoy, et al. - 2015 |

18 | Low-rank matrix recovery via iteratively reweighted least squares minimization,”
- Fornasier, Rauhut, et al.
- 2011
(Show Context)
Citation Context ...ficiently with various strategies [33, Chapter 15], [10, 23, 62, 71]. We note that several alternatives to nuclear norm minimization may also be applied including iteratively reweighted least squares =-=[32]-=-, iterative hard thresholding [47, 70], greedy approaches [51] and algorithms specialized to certain measurement maps A [43], but our analysis is geared towards nuclear norm minimization and does not ... |

18 |
Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding
- Matthews, Wehner, et al.
(Show Context)
Citation Context ...e PSymt denotes the projector onto the totally symmetric subspace Sym t of (Cn) ⊗t defined in the appendix – see equation (40). 4 RICHARD KUENG, HOLGER RAUHUT, AND ULRICH TERSTIEGE In accordance with =-=[55]-=-, we call a t-design proper, if all the weights are equal, i.e., pi = 1/N for all i = 1, . . . , N . Although exact, proper t-designs exist and can be constructed in any dimension n for any t ∈ N [66,... |

18 | Phase retrieval with application to optical imaging
- Shechtman, Eldar, et al.
(Show Context)
Citation Context ...trieving a complex signal from measurements that are ignorant towards phases is abundant in many different areas of science, such as X-ray cristallography [40, 57], astronomy [29] diffraction imaging =-=[67, 57]-=- and more [8, 12, 76]. Mathematically formulated, the problem consists of recovering a complex signal (vector) x ∈ Cn from measurements of the form |〈aj , x〉|2 = bj for j = 1, . . . ,m, (1) where a1, ... |

18 | User-Friendly Tools for Random Matrices: An Introduction,” manuscript - Tropp - 2012 |

16 |
Exact and approximate unitary 2-designs: constructions and applications, Phys
- Dankert, Cleve, et al.
(Show Context)
Citation Context ...to generate approximate t-designs is to consider arbitrary orbits of unitary t-designs. Unitary t-designs {pi, Ui}Ni=1 are a natural generalization of the spherical design concept to unitary matrices =-=[24, 36]-=-. They have the particular property that every weighted orbit {pi, Uix} with ‖x‖ℓ2 = 1 of an approximate unitary design forms an approximate complex projective t-design of the same accuracy. It was sh... |

16 |
Proximal algorithms. Foundations and Trends in Optimization
- Parikh, Boyd
- 2013
(Show Context)
Citation Context |

16 | Convex recovery of a structured signal from independent random linear measurements.
- Tropp
- 2014
(Show Context)
Citation Context ...stances have been identified for which nuclear norm minimization (4) – and potentially other algorithms – provably recovers the sought for low-rank matrix from considerably fewer than n2 measurements =-=[17, 16, 20, 35, 32, 52, 63, 74]-=-. All these constructions are based on randomness, the simplest being a random Gaussian measurement map where all entries Aj,k,ℓ in the representation A(X)j = ∑n k,ℓ=1Aj,k,ℓXk,ℓ are independent mean z... |

14 |
Construction of spherical t-designs,
- Bajnok
- 1992
(Show Context)
Citation Context ...[55], we call a t-design proper, if all the weights are equal, i.e., pi = 1/N for all i = 1, . . . , N . Although exact, proper t-designs exist and can be constructed in any dimension n for any t ∈ N =-=[66, 6, 45, 41]-=-, these constructions are typically inefficient in the sense that they require vector sets of exponential size. For example, the construction in [41] requires on the order of O (t)n vectors which scal... |

14 |
Evenly distributed unitaries: On the structure of unitary designs
- Gross, Audenaert, et al.
- 2007
(Show Context)
Citation Context ...to generate approximate t-designs is to consider arbitrary orbits of unitary t-designs. Unitary t-designs {pi, Ui}Ni=1 are a natural generalization of the spherical design concept to unitary matrices =-=[24, 36]-=-. They have the particular property that every weighted orbit {pi, Uix} with ‖x‖ℓ2 = 1 of an approximate unitary design forms an approximate complex projective t-design of the same accuracy. It was sh... |

14 | Normalized iterative hard thresholding for matrix completion.
- Tanner, Wei
- 2013
(Show Context)
Citation Context ...[33, Chapter 15], [10, 23, 62, 71]. We note that several alternatives to nuclear norm minimization may also be applied including iteratively reweighted least squares [32], iterative hard thresholding =-=[47, 70]-=-, greedy approaches [51] and algorithms specialized to certain measurement maps A [43], but our analysis is geared towards nuclear norm minimization and does not provide guarantees for these other alg... |

14 | Theory of Quantum Information, Lecture Notes, - Watrous - 2011 |

12 | A partial derandomization of phaselift using spherical designs, arXiv preprint arXiv:1310.2267
- Gross, Krahmer, et al.
- 2013
(Show Context)
Citation Context ...or) this obstacle could be overcome by providing problem specific recovery guarantees that either manifestly rely on (rank one) Gaussian measurements [13, 74] or result in a non-optimal sampling rate =-=[38, 15, 37]-=-. 1.3. Weighted complex projective designs. The concept of real spherical designs was introduced by Delsarte Goethals and Seidel in a seminal paper [26] and has been studied in algebraic combinatorics... |

12 |
Matrix recipes for hard thresholding methods,” arXiv:1203.4481
- Kyrillidis, Cevher
- 2012
(Show Context)
Citation Context ...[33, Chapter 15], [10, 23, 62, 71]. We note that several alternatives to nuclear norm minimization may also be applied including iteratively reweighted least squares [32], iterative hard thresholding =-=[47, 70]-=-, greedy approaches [51] and algorithms specialized to certain measurement maps A [43], but our analysis is geared towards nuclear norm minimization and does not provide guarantees for these other alg... |

11 |
Reexamination of optimal quantum state estimation of pure states,” Phys
- Hayashi, Hashimoto, et al.
- 2005
(Show Context)
Citation Context ...g theory [26, 59]. Recently, complex projective designs – the natural extension of real spherical designs to the complex unit sphere – have been of considerable interest in quantum information theory =-=[79, 65, 41, 36, 53, 11, 48]-=-. Roughly speaking, a complex projective t-design is a finite subset of the complex unit sphere in Cn with the particular property that the discrete average of any polynomial of degree (t, t) (i.e., a... |

8 |
Distinguishing multi-partite states by local measurements
- Lancien, Winter
- 2012
(Show Context)
Citation Context |

7 |
Local random quantum circuits are approximate polynomial-designs. ArXiv e-prints
- Brandao, Harrow, et al.
- 2012
(Show Context)
Citation Context |

7 | Sparse recovery under weak moment assumptions. arXiv:1401.2188,
- Lecue, Mendelson
- 2014
(Show Context)
Citation Context ... technique consists in the application of a uniform version of Tropp’s bowling scheme, see [74]. The crucial ingredient is a new method due to Mendelson [56] and Koltchiskii, Mendelson [44] (see also =-=[50]-=-) to obtain lower bounds for quantities of the form infu∈E ∑m j=1 |〈φj , x〉|2 where the φj are independent random vectors in R d and E is a subset of Rd. We start by recalling from [74] the notions an... |

7 |
The invariants of the Clifford groups, Des
- Nebe, Rains, et al.
(Show Context)
Citation Context ...projective designs. The concept of real spherical designs was introduced by Delsarte Goethals and Seidel in a seminal paper [26] and has been studied in algebraic combinatorics [68] and coding theory =-=[26, 59]-=-. Recently, complex projective designs – the natural extension of real spherical designs to the complex unit sphere – have been of considerable interest in quantum information theory [79, 65, 41, 36, ... |

6 |
Improved recovery guarantees for phase retrieval from coded diffraction patterns. arXiv preprint arXiv:1402.6286
- Gross, Krahmer, et al.
- 2014
(Show Context)
Citation Context ...or) this obstacle could be overcome by providing problem specific recovery guarantees that either manifestly rely on (rank one) Gaussian measurements [13, 74] or result in a non-optimal sampling rate =-=[38, 15, 37]-=-. 1.3. Weighted complex projective designs. The concept of real spherical designs was introduced by Delsarte Goethals and Seidel in a seminal paper [26] and has been studied in algebraic combinatorics... |

6 |
Chebyshev-type quadrature on multidimensional domains
- Korevaar, Meyers
- 1994
(Show Context)
Citation Context ...[55], we call a t-design proper, if all the weights are equal, i.e., pi = 1/N for all i = 1, . . . , N . Although exact, proper t-designs exist and can be constructed in any dimension n for any t ∈ N =-=[66, 6, 45, 41]-=-, these constructions are typically inefficient in the sense that they require vector sets of exponential size. For example, the construction in [41] requires on the order of O (t)n vectors which scal... |

5 | Signal reconstruction from the magnitude of subspace components, arXiv
- Bachoc, Ehler
- 2013
(Show Context)
Citation Context ...s by drawing sufficiently many vectors at random and afterwards solving a linear system for the weights. Further note, that generalizations of cubatures to higher dimensional projections were used in =-=[5]-=- in the context of a generalized phase retrieval problem, where the measurements are given as norms of projections onto higher dimensional subspaces. 2. Main results 2.1. Low rank matrix recovery from... |

5 | Large Deviation Bounds for k-designs
- Low
- 2009
(Show Context)
Citation Context |

4 |
The power of matrix completion: near-optimal convex relaxation
- Candès, Tao
(Show Context)
Citation Context ...rements provide optimal guarantees, which are comparably easy to derive, many applications demand for more structure in the measurement process. A particular instance is the matrix completion problem =-=[22, 17, 19, 35, 21]-=-, which aims at recovering missing entries of a matrix which is known to be of low rank. Here, the source of randomness is in the selection of the known entries. In contrast to the unstructured measur... |

4 |
Numerical cubature using error-correcting codes
- Kuperberg
(Show Context)
Citation Context ...ould be much stronger if an efficient protocol for the corresponding POVM measurements could be provided. We leave this for future work. Alternatively, the authors of [3] mention results by Kuperberg =-=[46]-=- who managed to construct exact t-designs containing only O (n2t) vectors. They furthermore conjecture that their method of efficiently implementing the corresponding POVM measurement also works for K... |

4 | Pseudo-randomness and Learning in Quantum Computation
- Low
- 2010
(Show Context)
Citation Context ...f∥∥∥∥∥ N∑ i=1 pi (wiw ∗ i ) ⊗t − ∫ CPn−1 (ww∗)⊗t dw ∥∥∥∥∥ p ≤ ( n+ t− 1 t )−1 θp. (10) While accuracy measured in arbitrary Schatten-p-norms is conceivable, the ones measured in operator norm (p = ∞) =-=[42, 3, 54, 11]-=- and nuclear norm (p = 1) [58] are the ones most commonly used – at least in quantum information theory. For these two accuracies, the definition in particular assures that every approximate t-design ... |

4 |
Spherical 7-designs in 2n-dimensional Euclidean space
- Sidelnikov
- 1999
(Show Context)
Citation Context ... 1.3. Weighted complex projective designs. The concept of real spherical designs was introduced by Delsarte Goethals and Seidel in a seminal paper [26] and has been studied in algebraic combinatorics =-=[68]-=- and coding theory [26, 59]. Recently, complex projective designs – the natural extension of real spherical designs to the complex unit sphere – have been of considerable interest in quantum informati... |

2 |
Phase retrieval by iterated projections
- Gerchberg, Saxton
- 1972
(Show Context)
Citation Context ...s that the signal x enters the measurement process (1) quadratically. This leads to a non-linear inverse problem. Classical approaches to numerically solving it include alternating projection methods =-=[30, 34]-=-. However, these methods usually require extra constraints and careful selection of parameters, and in particular, no rigorous convergence or recovery guarantees seem to be available. As Balan et al. ... |

2 |
Experimental comparison of efficient tomography schemes for a six-qubit state
- Schwemmer, Tóth, et al.
(Show Context)
Citation Context ... issues are well understood [31] and Y.K. Liu managed to prove a uniform recovery guarantee [52] which is comparable to the results presented here. Also, this procedure has been tested in experiments =-=[64]-=-. Theorem 5 is similar in spirit and we show here that it permits efficient low rank quantum state tomography for different types of measurements. Indeed, in the field of quantum information theory, v... |

1 |
Solving quadratic efquations via PhaseLift when there are about as many equations as unknowns
- Candès, Li
- 2013
(Show Context)
Citation Context ... of interest is by construction a rank-one projector) this obstacle could be overcome by providing problem specific recovery guarantees that either manifestly rely on (rank one) Gaussian measurements =-=[13, 74]-=- or result in a non-optimal sampling rate [38, 15, 37]. 1.3. Weighted complex projective designs. The concept of real spherical designs was introduced by Delsarte Goethals and Seidel in a seminal pape... |

1 |
Incoherence-optimal matrix completion. preprint arXiv:1310.0154
- Chen
- 2013
(Show Context)
Citation Context ...rements provide optimal guarantees, which are comparably easy to derive, many applications demand for more structure in the measurement process. A particular instance is the matrix completion problem =-=[22, 17, 19, 35, 21]-=-, which aims at recovering missing entries of a matrix which is known to be of low rank. Here, the source of randomness is in the selection of the known entries. In contrast to the unstructured measur... |

1 | Completing any low-rank matrix, provably
- Chen, Bhojanapalli, et al.
- 2013
(Show Context)
Citation Context ...rements provide optimal guarantees, which are comparably easy to derive, many applications demand for more structure in the measurement process. A particular instance is the matrix completion problem =-=[22, 17, 19, 35, 21]-=-, which aims at recovering missing entries of a matrix which is known to be of low rank. Here, the source of randomness is in the selection of the known entries. In contrast to the unstructured measur... |

1 |
Generating a state t-design by diagonal quantum circuits
- Nakata, Koashi, et al.
(Show Context)
Citation Context ...(ww∗)⊗t dw ∥∥∥∥∥ p ≤ ( n+ t− 1 t )−1 θp. (10) While accuracy measured in arbitrary Schatten-p-norms is conceivable, the ones measured in operator norm (p = ∞) [42, 3, 54, 11] and nuclear norm (p = 1) =-=[58]-=- are the ones most commonly used – at least in quantum information theory. For these two accuracies, the definition in particular assures that every approximate t-design is in particular also a k-desi... |