The nonconvex formulation of the matrix completion problem has received significant attention in recent years due to its affordable complexity compared to the convex formulation. Gradient Descent (GD) is a simple yet efficient baseline algorithm for solving nonconvex optimization problems. The success of GD has been witnessed in many different problems in both theory and practice when it is combined with random initialization. However, previous works on matrix completion require either careful initialization or regularizers to prove the convergence of GD. In this paper, we study the rank-1 symmetric matrix completion and prove that GD converges to the ground truth when small random initialization is used. We show that in a logarithmic number of iterations, the trajectory enters the region where local convergence occurs. We provide an upper bound on the initialization size that is sufficient to guarantee the convergence, and show that a larger initialization can be used as more samples are available. We observe that the implicit regularization effect of GD plays a critical role in the analysis, and for the entire trajectory, it prevents each entry from becoming much larger than the others.

We consider a query-based data acquisition problem for binary classification of unknown labels, which has diverse applications in communications, crowdsourcing, recommender systems and active learning. To ensure reliable recovery of unknown labels with as few number of queries as possible, we consider an effective query type that asks “group attribute” of a chosen subset of objects. In particular, we consider the problem of classifying m binary labels with XOR queries that ask whether the number of objects having a given attribute in the chosen subset of size d is even or odd. The subset size d, which we call query degree, can be varying over queries. We consider a general noise model where the accuracy of answers on queries changes depending both on the worker (the data provider) and query degree d. For this general model, we characterize the information-theoretic limit on the optimal number of queries to reliably recover m labels in terms of a given combination of degree-d queries and noise parameters. Further, we propose an efficient inference algorithm that achieves this limit even when the noise parameters are unknown.

We consider the crowdsourced classification of m binary labels with XOR queries that ask whether the number of objects having a given attribute in the chosen subset of size d is even or odd. The subset size d, which we call query degree, can be varying over queries. Since a worker needs to make more efforts to answer a query of a higher degree, we consider a noise model where the accuracy of worker's answer changes depending both on the worker reliability and query degree d. For this general model, we characterize the information-theoretic limit on the optimal number of queries to reliably recover m labels in terms of a given combination of degree-d queries and noise parameters. Further, we propose an efficient inference algorithm that achieves this limit even when the noise parameters are unknown.1

This paper introduces a high rate error-correcting coding scheme called symmetric block-wise concatenated Bose-Chaudhuri-Hocquenghem (symmetric BC-BCH) codes tailored for storage devices with hard-decision outputs, e.g., storage devices based on NAND flash memory. It will be shown that a careful integration of the symmetry and 2-D block-wise concatenation is especially beneficial to achieve improvements of error-rate performance when an iterative hard-decision-based decoding (IHDD) is assumed. The claim is substantiated by proving that the proposed symmetric concatenation is optimal in terms of error-rate performance in the low error-rate regime over other 2-D block-wise concatenations. Besides, this paper proposes a novel way to design constituent codes, which enables us to enjoy advantages of primitive BCH codes and to efficiently break stopping sets associated with the IHDD in the low error-rate regime. We consider error-control systems made up of a symmetric BC-BCH code, the IHDD, and simple auxiliary decoders specifically targeting to break stopping sets caused in the IHDD. It will be shown that the auxiliary decoders significantly improve error-rate performance at a negligible amount of extra complexity. Performance comparisons are also carried out between error-control systems with the proposed and other coding schemes such as BCH codes, quasi-primitive BC-BCH codes, and low-density parity-check codes.

In this work, we study high-rate error-control systems with serial quasi-primitive block-wise concatenated Bose-Chaudhuri-Hocquenghem (BC-BCH) codes for storage devices using multi-level per cell (MLC) NAND flash memories. The system targets at achieving a strong error-correcting capability when only hard-decision channel outputs are available. Error-rate performance of the proposed system is compared with those of systems based on various coding schemes including LDPC codes.

In this work, we propose a novel design rule of block-wise concatenated Bose-Chaudhuri-Hocquenghem (BC-BCH) codes for storage devices using multi-level per cell (MLC) NAND flash memories. BC-BCH codes designed in accordance with the proposed design rule are called quasi-primitive BC-BCH codes in which constituent BCH codes are deliberately chosen for their lengths to be as close to primitive BCH codes as possible. It will be shown that such quasi-primitive BC-BCH codes can achieve significant improvements of error-correcting capability over the existing BC-BCH codes when an iterative hard-decision based decoding (IHDD) is assumed. In addition, we propose a novel collaborative decoding algorithm which targets at resolving dominant error patterns associated with the IHDD. Error-rate performances of error-control systems with the proposed quasi-primitive BC-BCH and existing BC-BCH codes are compared. For more comprehensive performance comparisons, systems with a hypothetically long BCH code and a product code are also considered in the comparisons.

In this work, we consider high-rate error-control systems based on block-wise concatenated Bose-Chaudhuri-Hocquenghem (BC-BCH) codes with iterative hard-decision decoding (IHDD) for storage devices using multi-level per cell (MLC) NAND flash memories. In particular, we propose a novel design rule of BC-BCH codes which consists of quasi-primitive BCH codes and block-wise concatenation of the constituent codes. Comprehensive performance comparisons are carried out among error-control systems with various coding schemes such as BC-BCH codes and LDPC codes.

In this work, we consider high-rate error-control systems for storage devices using multi-level per cell (MLC) NAND flash memories. Aiming at achieving a strong error-correcting capability, we propose error-control systems using block-wise parallel/serial concatenations of short Bose-Chaudhuri-Hocquenghem (BCH) codes with two iterative decoding strategies, namely, iterative hard-decision decoding (IHDD) and iterative reliability based decoding (IRBD). It will be shown that a simple but very efficient IRBD is possible by taking advantage of a unique feature of the block-wise concatenation. For tractable performance analysis and design of IHDD and IRBD at very low error rates, we derive semi-analytic approaches. The proposed error-control systems are compared with various error-control systems with well-known coding schemes such as a product code, multiple BCH codes, a single long BCH code, and low-density parity-check codes in terms of page error rates, which confirms our claim: the proposed error-control systems achieve good tradeoffs between error-performance and complexity as compared to the traditional schemes and is also very favorable for implementation.

In this work, we propose a scheme to extract soft information from hard-decision outputs in multi-level per cell (MLC) flash memory based on a cell-to-cell interference model. It will be shown that the soft information extracted in the form of log-likelihood ratio (LLR) by taking into account a dominant cell-to-cell interference term provides significant performance improvements when the error-control system is designed with an error-correcting code with iterative decoding algorithm, e.g. low-density parity-check (LDPC) code with the Belief-Propagation (BP) algorithm. To confirm the claims, we design error-control systems with a conventional Bose-Chaudhuri-Hocquenghem (BCH) code and an LDPC code with/without the soft information extraction. Performances of the systems are extensively evaluated and compared, which clearly shows that the soft information extraction based on the cell-to-cell interference model leads to a considerably better performance.