Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHow Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?
197
0
0.0
(
0
)
Added by
Richard Zhang
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
When the linear measurements of an instance of low-rank matrix recovery satisfy a restricted isometry property (RIP)---i.e. they are approximately norm-preserving---the problem is known to contain no spurious local minima, so exact recovery is guaranteed. In this paper, we show that moderate RIP is not enough to eliminate spurious local minima, so existing results can only hold for near-perfect RIP. In fact, counterexamples are ubiquitous: we prove that every x is the spurious local minimum of a rank-1 instance of matrix recovery that satisfies RIP. One specific counterexample has RIP constant $delta=1/2$, but causes randomly initialized stochastic gradient descent (SGD) to fail 12% of the time. SGD is frequently able to avoid and escape spurious local minima, but this empirical result shows that it can occasionally be defeated by their existence. Hence, while exact recovery guarantees will likely require a proof of no spurious local minima, arguments based solely on norm preservation will only be applicable to a narrow set of nearly-isotropic instances.
rate research
Read More
Nonconvex matrix recovery is known to contain no spurious local minima under a restricted isometry property (RIP) with a sufficiently small RIP constant $delta$. If $delta$ is too large, however, then counterexamples containing spurious local minima are known to exist. In this paper, we introduce a proof technique that is capable of establishing sharp thresholds on $delta$ to guarantee the inexistence of spurious local minima. Using the technique, we prove that in the case of a rank-1 ground truth, an RIP constant of $delta<1/2$ is both necessary and sufficient for exact recovery from any arbitrary initial point (such as a random point). We also prove a local recovery result: given an initial point $x_{0}$ satisfying $f(x_{0})le(1-delta)^{2}f(0)$, any descent algorithm that converges to second-order optimality guarantees exact recovery.
A pair of quantum observables diagonal in the same incoherent basis can be measured jointly, so some coherence is obviously required for measurement incompatibility. Here we first observe that coherence in a single observable is linked to the diagonal elements of any observable jointly measurable with it, leading to a general criterion for the coherence needed for incompatibility. Specialising to the case where the second observable is incoherent (diagonal), we develop a concrete method for solving incompatibility problems, tractable even in large systems by analytical bounds, without resorting to numerical optimisation. We verify the consistency of our method by a quick proof of the known noise bound for mutually unbiased bases, and apply it to study emergent classicality in the spin-boson model of an N-qubit open quantum system. Finally, we formulate our theory in an operational resource-theoretic setting involving genuinely incoherent operations used previously in the literature, and show that if the coherence is insufficient to sustain incompatibility, the associated joint measurements have sequential implementations via incoherent instruments.
Matrices satisfying the Restricted Isometry Property (RIP) play an important role in the areas of compressed sensing and statistical learning. RIP matrices with optimal parameters are mainly obtained via probabilistic arguments, as explicit constructions seem hard. It is therefore interesting to ask whether a fixed matrix can be incorporated into a construction of restricted isometries. In this paper, we construct a new broad ensemble of random matrices with dependent entries that satisfy the restricted isometry property. Our construction starts with a fixed (deterministic) matrix $X$ satisfying some simple stable rank condition, and we show that the matrix $XR$, where $R$ is a random matrix drawn from various popular probabilistic models (including, subgaussian, sparse, low-randomness, satisfying convex concentration property), satisfies the RIP with high probability. These theorems have various applications in signal recovery, random matrix theory, dimensionality reduction, etc. Additionally, motivated by an application for understanding the effectiveness of word vector embeddings popular in natural language processing and machine learning applications, we investigate the RIP of the matrix $XR^{(l)}$ where $R^{(l)}$ is formed by taking all possible (disregarding order) $l$-way entrywise products of the columns of a random matrix $R$.
Blockchain is built on a peer-to-peer network that relies on frequent communications among the distributively located nodes. In particular, the consensus mechanisms (CMs), which play a pivotal role in blockchain, are communication resource-demanding and largely determines blockchain security bound and other key performance metrics such as transaction throughput, latency and scalability. Most blockchain systems are designed in a stable wired communication network running in advanced devices under the assumption of sufficient communication resource provision. However, it is envisioned that the majority of the blockchain node peers will be connected through the wireless network in the future. Constrained by the highly dynamic wireless channel and scarce frequency spectrum, communication can significantly affect blockchains key performance metrics. Hence, in this paper, we present wireless blockchain networks (WBN) under various commonly used CMs and we answer the question of how much communication resource is needed to run such a network. We first present the role of communication in the four stages of the blockchain procedure. We then discuss the relationship between the communication resource provision and the WBNs performance, for three of the most used blockchain CMs namely, Proof-of-Work (PoW), practical Byzantine Fault Tolerant (PBFT) and Raft. Finally, we provide analytical and simulated results to show the impact of the communication resource provision on blockchain performance.
Matrix completion has attracted much interest in the past decade in machine learning and computer vision. For low-rank promotion in matrix completion, the nuclear norm penalty is convenient due to its convexity but has a bias problem. Recently, various algorithms using nonconvex penalties have been proposed, among which the proximal gradient descent (PGD) algorithm is one of the most efficient and effective. For the nonconvex PGD algorithm, whether it converges to a local minimizer and its convergence rate are still unclear. This work provides a nontrivial analysis on the PGD algorithm in the nonconvex case. Besides the convergence to a stationary point for a generalized nonconvex penalty, we provide more deep analysis on a popular and important class of nonconvex penalties which have discontinuous thresholding functions. For such penalties, we establish the finite rank convergence, convergence to restricted strictly local minimizer and eventually linear convergence rate of the PGD algorithm. Meanwhile, convergence to a local minimizer has been proved for the hard-thresholding penalty. Our result is the first shows that, nonconvex regularized matrix completion only has restricted strictly local minimizers, and the PGD algorithm can converge to such minimizers with eventually linear rate under certain conditions. Illustration of the PGD algorithm via experiments has also been provided. Code is available at https://github.com/FWen/nmc.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
