Improving compressed sensing with the diamond norm

Abstract

In low-rank matrix recovery, one aims to reconstruct a low-rank matrix from a minimal number of linear measurements. Within the paradigm of compressed sensing, this is made computationally efficient by minimizing the nuclear norm as a convex surrogate for rank. In this work, we identify an improved regularizer based on the so-called diamond norm, a concept imported from quantum information theory. We show that -for a class of matrices saturating a certain norm inequality- the descent cone of the diamond norm is contained in that of the nuclear norm. This suggests superior reconstruction properties for these matrices. We explicitly characterize this set of matrices. Moreover, we demonstrate numerically that the diamond norm indeed outperforms the nuclear norm in a number of relevant applications: These include signal analysis tasks such as blind matrix deconvolution or the retrieval of certain unitary basis changes, as well as the quantum information problem of process tomography with random measurements. The diamond norm is defined for matrices that can be interpreted as order-4 tensors and it turns out that the above condition depends crucially on that tensorial structure. In this sense, this work touches on an aspect of the notoriously difficult tensor completion problem.

25 pages + Appendix, 7 Figures, published version

References in corpus (12)

• Regularized estimation of large covariance matrices
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Evenly distributed unitaries: on the structure of unitary designs
• Self-Calibration and Biconvex Compressive Sensing
• A positive tensor network approach for simulating open quantum many-body systems
• Multiqubit Clifford groups are unitary 3-designs
• Comparing Experiments to the Fault-Tolerance Threshold
• Process POVM: A mathematical framework for the description of process tomography experiments
• Accelerated Randomized Benchmarking
• Simpler semidefinite programs for completely bounded norms
• Note on the saturation of the norm inequalities between diamond and nuclear norm
• On the complexity of approximating the diamond norm

Cited by in corpus (11)

• Models of quantum complexity growth
• ${\ell }_0$-Motivated Low-Rank Sparse Subspace Clustering
• Recovering quantum gates from few average gate fidelities
• Experimentally exploring compressed sensing quantum tomography
• Randomized benchmarking for individual quantum gates
• Almost all quantum channels are equidistant
• Guaranteed recovery of quantum processes from few measurements
• Operational applications of the diamond norm and related measures in quantifying the non-physicality of quantum maps
• Compressive gate set tomography
• Note on the saturation of the norm inequalities between diamond and nuclear norm
• Five Starter Pieces: Quantum Information Science via Semi-definite Programs