The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
This paper studies the following question: where should an adversary place an outlier of a given magnitude in order to maximize the error of the subspace estimated by PCA? We give the exact location of this worst possible outlier, and the exact expression of the maximum possible error. Equivalently, we determine the information-theoretic bounds on how much an outlier can tilt a subspace in its direction...
In this paper we present a simple and efficient method to compute the canonical polyadic decomposition (CPD) of generic low-rank tensors using elementary linear algebra. The key insight is that all the columns in a low-rank tensor lie in a low-dimensional subspace, and that the coefficients of the columns in each slice with respect to the right basis are scaled copies of one an other. The basis, together...
In many practical applications, one is given a subset Ω of the entries in a d × N data matrix X, and aims to infer all the missing entries. Existing theory in low-rank matrix completion (LRMC) provides conditions on X (e.g., bounded coherence or genericity) and Ω (e.g., uniform random sampling or deterministic combinatorial conditions) to guarantee that if X is rank-r, then X is the only rank-r matrix...
Low-rank matrix completion (LRMC) problems arise in a wide variety of applications. Previous theory mainly provides conditions for completion under missing-at-random samplings. This paper studies deterministic conditions for completion. An incomplete $d \times N$ matrix is finitely rank-$r$ completable if there are at most finitely many rank-$r$ matrices that agree with all its observed entries. Finite...
In this paper we propose a novel adaptive algorithm that provably performs low-rank matrix completion (LRMC) from restricted sets of observations, under ideal or noisy measurements, in lieu of coherence assumptions, with minimal sampling rates and optimal computational complexity. We discuss the main advantages of the adaptive setting of LRMC, and complement our theoretical analysis with experiments,...
Low-rank matrix completion (LRMC) problems arise in a wide variety of applications. Previous theory mainly provides conditions for completion under missing-at-random samplings. This paper studies deterministic conditions for completion. An incomplete d × N matrix is finitely rank-r completable if there are at most finitely many rank-r matrices that agree with all its observed entries. Finite completability...
Consider an r-dimensional subspace of ℝd, r < d, and suppose that we are only given projections of this subspace onto small subsets of the canonical coordinates. The paper establishes necessary and sufficient deterministic conditions on the subsets for subspace identifiability. The results also shed new light on low-rank matrix completion.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.