In practical compressed sensing (CS), the obtained measurements typically necessitate quantization to a limited number of bits prior to transmission or storage. This nonlinear quantization process poses significant recovery challenges, particularly with extreme coarse quantization such as 1-bit. Recently, an efficient algorithm called QCS-SGM was proposed for quantized CS (QCS) which utilizes score-based generative models (SGM) as an implicit prior. Due to the adeptness of SGM in capturing the intricate structures of natural signals, QCS-SGM substantially outperforms previous QCS methods. However, QCS-SGM is constrained to (approximately) row-orthogonal sensing matrices as the computation of the likelihood score becomes intractable otherwise. To address this limitation, we introduce an advanced variant of QCS-SGM, termed QCS-SGM+, capable of handling general matrices effectively. The key idea is a Bayesian inference perspective on the likelihood score computation, wherein expectation propagation is employed for its approximate computation. Extensive experiments are conducted, demonstrating the substantial superiority of QCS-SGM+ over QCS-SGM for general sensing matrices beyond mere row-orthogonality.

We theoretically analyze the model selection consistency of least absolute shrinkage and selection operator (Lasso), both with and without post-thresholding, for high-dimensional Ising models. For random regular (RR) graphs of size $p$ with regular node degree $d$ and uniform couplings $\theta_0$, it is rigorously proved that Lasso without post-thresholding is model selection consistent in the whole paramagnetic phase with the same order of sample complexity $n=\Omega{(d^3\log{p})}$ as that of $\ell_1$-regularized logistic regression ($\ell_1$-LogR). This result is consistent with the conjecture in Meng, Obuchi, and Kabashima 2021 using the non-rigorous replica method from statistical physics and thus complements it with a rigorous proof. For general tree-like graphs, it is demonstrated that the same result as RR graphs can be obtained under mild assumptions of the dependency condition and incoherence condition. Moreover, we provide a rigorous proof of the model selection consistency of Lasso with post-thresholding for general tree-like graphs in the paramagnetic phase without further assumptions on the dependency and incoherence conditions. Experimental results agree well with our theoretical analysis.

We analyze the performance of the least absolute shrinkage and selection operator (Lasso) for the linear model when the number of regressors $N$ grows larger keeping the true support size $d$ finite, i.e., the ultra-sparse case. The result is based on a novel treatment of the non-rigorous replica method in statistical physics, which has been applied only to problem settings where $N$, $d$ and the number of observations $M$ tend to infinity at the same rate. Our analysis makes it possible to assess the average performance of Lasso with Gaussian sensing matrices without assumptions on the scaling of $N$ and $M$, the noise distribution, and the profile of the true signal. Under mild conditions on the noise distribution, the analysis also offers a lower bound on the sample complexity necessary for partial and perfect support recovery when $M$ diverges as $M = O(\log N)$. The obtained bound for perfect support recovery is a generalization of that given in previous literature, which only considers the case of Gaussian noise and diverging $d$. Extensive numerical experiments strongly support our analysis.

We study the inference problem in the noisy group testing to identify defective items from the perspective of the decision theory. We introduce Bayesian inference and consider the Bayesian optimal setting in which the true generative process of the test results is known. We demonstrate the adequacy of the posterior marginal probability in the Bayesian optimal setting as a diagnostic variable based on the area under the curve (AUC). Using the posterior marginal probability, we derive the general expression of the optimal cutoff value that yields the minimum expected risk function. Furthermore, we evaluate the performance of the Bayesian group testing without knowing the true states of the items: defective or non-defective. By introducing an analytical method from statistical physics, we derive the receiver operating characteristics curve, and quantify the corresponding AUC under the Bayesian optimal setting. The obtained analytical results precisely describes the actual performance of the belief propagation algorithm defined for single samples when the number of items is sufficiently large.

In this study, macroscopic properties of the vector approximate message passing (VAMP) algorithm for inference of generalized linear models are investigated using a non-rigorous heuristic method of statistical mechanics when the true posterior cannot be used and the measurement matrix is a sample from rotation-invariant random matrix ensembles. The focus is on the correspondence between the non-rigorous replica analysis of statistical mechanics and the performance assessment of VAMP in the model-mismatched setting. The correspondence of this kind is well-known when the measurement matrix has independent and identically distributed entries. However, when the measurement matrix follows a general rotation-invariant matrix ensemble, the correspondence has been validated only under limited cases, such as the Bayes optimal inference or the convex empirical risk minimization. The result presented in this paper is to extend the scope of such correspondence. Herein, we heuristically derive the explicit formula of state-evolution equations, which macroscopically describe VAMP dynamics for the current model-mismatched case, and show that their fixed point is generally consistent with the replica symmetric solution obtained by the replica method of statistical mechanics. We also show that the fixed point of VAMP can exhibit a microscopic instability, which indicates that message variables continue to move by VAMP while their macroscopically summarized quantities converge to fixed values. The critical condition the for microscopic instability agrees with that for breaking the replica symmetry that is derived within the non-rigorous replica analysis. The results of the numerical experiments cross-check our findings.

We theoretically analyze the typical learning performance of $\ell_{1}$-regularized linear regression ($\ell_1$-LinR) for Ising model selection using the replica method from statistical mechanics. For typical random regular graphs in the paramagnetic phase, an accurate estimate of the typical sample complexity of $\ell_1$-LinR is obtained. Remarkably, despite the model misspecification, $\ell_1$-LinR is model selection consistent with the same order of sample complexity as $\ell_{1}$-regularized logistic regression ($\ell_1$-LogR), i.e., $M=\mathcal{O}\left(\log N\right)$, where $N$ is the number of variables of the Ising model. Moreover, we provide an efficient method to accurately predict the non-asymptotic behavior of $\ell_1$-LinR for moderate $M, N$, such as precision and recall. Simulations show a fairly good agreement between theoretical predictions and experimental results, even for graphs with many loops, which supports our findings. Although this paper mainly focuses on $\ell_1$-LinR, our method is readily applicable for precisely characterizing the typical learning performances of a wide class of $\ell_{1}$-regularized $M$-estimators including $\ell_1$-LogR and interaction screening.

Vector approximate message passing (VAMP) is an efficient approximate inference algorithm used for generalized linear models. Although VAMP exhibits excellent performance, particularly when measurement matrices are sampled from rotationally invariant ensembles, existing convergence and performance analyses have been limited mostly to cases in which the correct posterior distribution is available. Here, we extend the analyses for cases in which the correct posterior distribution is not used in the inference stage. We derive state evolution equations, which macroscopically describe the dynamics of VAMP, and show that their fixed point is consistent with the replica symmetric solution obtained by the replica method of statistical mechanics. We also show that the fixed point of VAMP can exhibit a microscopic instability, the critical condition of which agrees with that for breaking the replica symmetry. The results of numerical experiments support our findings.

Recent remarkable advances in experimental techniques have provided a background for inferring neuronal couplings from point process data that include a great number of neurons. Here, we propose a systematic procedure for pre- and postprocessing generic point process data in an objective manner to handle data in the framework of a binary simple statistical model, the Ising or generalized McCulloch-Pitts model. The procedure has two steps: (1) determining time bin size for transforming the point process data into discrete-time binary data and (2) screening relevant couplings from the estimated couplings. For the first step, we decide the optimal time bin size by introducing the null hypothesis that all neurons would fire independently, then choosing a time bin size so that the null hypothesis is rejected with the strict criteria. The likelihood associated with the null hypothesis is analytically evaluated and used for the rejection process. For the second postprocessing step, after a certain estimator of coupling is obtained based on the preprocessed data set (any estimator can be used with the proposed procedure), the estimate is compared with many other estimates derived from data sets obtained by randomizing the original data set in the time direction. We accept the original estimate as relevant only if its absolute value is sufficiently larger than those of randomized data sets. These manipulations suppress false positive couplings induced by statistical noise. We apply this inference procedure to spiking data from synthetic and in vitro neuronal networks. The results show that the proposed procedure identifies the presence or absence of synaptic couplings fairly well, including their signs, for the synthetic and experimental data. In particular, the results support that we can infer the physical connections of underlying systems in favorable situations, even when using a simple statistical model.

An approximate method for conducting resampling in Lasso, the $\ell_1$ penalized linear regression, in a semi-analytic manner is developed, whereby the average over the resampled datasets is directly computed without repeated numerical sampling, thus enabling an inference free of the statistical fluctuations due to sampling finiteness, as well as a significant reduction of computational time. The proposed method is based on a message passing type algorithm, and its fast convergence is guaranteed by the state evolution analysis, when covariates are provided as zero-mean independently and identically distributed Gaussian random variables. It is employed to implement bootstrapped Lasso (Bolasso) and stability selection, both of which are variable selection methods using resampling in conjunction with Lasso, and resolves their disadvantage regarding computational cost. To examine approximation accuracy and efficiency, numerical experiments were carried out using simulated datasets. Moreover, an application to a real-world dataset, the wine quality dataset, is presented. To process such real-world datasets, an objective criterion for determining the relevance of selected variables is also introduced by the addition of noise variables and resampling. MATLAB codes implementing the proposed method are distributed in (Obuchi, 2018).

Inferring directional couplings from the spike data of networks is desired in various scientific fields such as neuroscience. Here, we apply a recently proposed objective procedure to the spike data obtained from the Hodgkin-Huxley type models and in vitro neuronal networks cultured in a circular structure. As a result, we succeed in reconstructing synaptic connections accurately from the evoked activity as well as the spontaneous one. To obtain the results, we invent an analytic formula approximately implementing a method of screening relevant couplings. This significantly reduces the computational cost of the screening method employed in the proposed objective procedure, making it possible to treat large-size systems as in this study.

We develop an approximate formula for evaluating a cross-validation estimator of predictive likelihood for multinomial logistic regression regularized by an $\ell_1$-norm. This allows us to avoid repeated optimizations required for literally conducting cross-validation; hence, the computational time can be significantly reduced. The formula is derived through a perturbative approach employing the largeness of the data size and the model dimensionality. An extension to the elastic net regularization is also addressed. The usefulness of the approximate formula is demonstrated on simulated data and the ISOLET dataset from the UCI machine learning repository. MATLAB and python codes implementing the approximate formula are distributed in (Obuchi, 2017; Takahashi and Obuchi, 2017).

We analyze the matrix factorization problem. Given a noisy measurement of a product of two matrices, the problem is to estimate back the original matrices. It arises in many applications, such as dictionary learning, blind matrix calibration, sparse principal component analysis, blind source separation, low rank matrix completion, robust principal component analysis, or factor analysis. It is also important in machine learning: unsupervised representation learning can often be studied through matrix factorization. We use the tools of statistical mechanics-the cavity and replica methods-to analyze the achievability and computational tractability of the inference problems in the setting of Bayes-optimal inference, which amounts to assuming that the two matrices have random-independent elements generated from some known distribution, and this information is available to the inference algorithm. In this setting, we compute the minimal mean-squared-error achievable, in principle, in any computational time, and the error that can be achieved by an efficient approximate message passing algorithm. The computation is based on the asymptotic state-evolution analysis of the algorithm. The performance that our analysis predicts, both in terms of the achieved mean-squared-error and in terms of sample complexity, is extremely promising and motivating for a further development of the algorithm.

The performance of regularized least-squares estimation in noisy compressed sensing is analyzed in the limit when the dimensions of the measurement matrix grow large. The sensing matrix is considered to be from a class of random ensembles that encloses as special cases standard Gaussian, row-orthogonal, geometric, and so-called T-orthogonal constructions. Source vectors that have non-uniform sparsity are included in the system model. Regularization based on ℓ-norm and leading to LASSO estimation, or basis pursuit denoising, is given the main emphasis in the analysis. Extensions to ℓ-norm and zero-norm regularization are also briefly discussed. The analysis is carried out using the replica method in conjunction with some novel matrix integration results. Numerical experiments for LASSO are provided to verify the accuracy of the analytical results. The numerical experiments show that for noisy compressed sensing, the standard Gaussian ensemble is a suboptimal choice for the measurement matrix. Orthogonal constructions provide a superior performance in all considered scenarios and are easier to implement in practical applications. It is also discovered that for non-uniform sparsity patterns, the T-orthogonal matrices can further improve the mean square error behavior of the reconstruction when the noise level is not too high. However, as the additive noise becomes more prominent in the system, the simple row-orthogonal measurement matrix appears to be the best choice out of the considered ensembles.

We develop a method for evaluating restricted isometry constants (RICs). This evaluation is reduced to the identification of the zero-points of entropy density which is defined for submatrices that are composed of columns selected from a given measurement matrix. Using the replica method developed in statistical mechanics, we assess RICs for Gaussian random matrices under the replica symmetric (RS) assumption. In order to numerically validate the adequacy of our analysis, we employ the exchange Monte Carlo (EMC) method, which has been empirically demonstrated to achieve much higher numerical accuracy than naive Monte Carlo methods. The EMC method suggests that our theoretical estimation of an RIC corresponds to an upper bound that is tighter than in preceding studies. Physical consideration indicates that our assessment of the RIC could be improved by taking into account the replica symmetry breaking.

A signal recovery scheme is developed for linear observation systems based on expectation consistent (EC) mean field approximation. Approximate message passing (AMP) is known to be consistent with the results obtained using the replica theory, which is supposed to be exact in the large system limit, when each entry of the observation matrix is independently generated from an identical distribution. However, this is not necessarily the case for general matrices. We show that EC recovery exhibits consistency with the replica theory for a wider class of random observation matrices. This is numerically confirmed by experiments for the Bayesian optimal signal recovery of compressed sensing using random row-orthogonal matrices.

Performance of regularized least-squares estimation in noisy compressed sensing is studied in the limit when the problem dimensions grow large. The sensing matrix is sampled from the rotationally invariant ensemble that encloses as special cases the standard IID and row-orthogonal constructions. The analysis is carried out using the replica method in conjunction with some novel matrix integration results. The numerical experiments show that for noisy compressed sensing, the standard IID ensemble is a suboptimal choice for the measurement matrix. Orthogonal constructions provide a superior performance in all considered scenarios and are easier to implement in practice.

We consider a learning problem of identifying a dictionary matrix D ∈ RM×Nfrom a sample set of M dimensional vectors Y ∈ RM×P= N-1/2DX ∈ RM×P, where X ∈ RN×pis a sparse matrix in which the density of non-zero entries is 0c(sample complexity) necessary for perfectly identifying D of the optimal learning scheme when D and X are independently generated from certain distributions. By using the replica method of statistical mechanics, we show that Pc~ O(N) holds as long as α = M/N > ρ is satisfied in the limit of N → ∞. Our analysis also implies that the posterior distribution given Y is condensed only at the correct dictionary D when the compression rate α is greater than a certain critical value αM(p). This suggests that belief propagation may allow us to learn D with a low computational complexity using O(N) samples.

The Flexible Wireless System (FWS) has been proposed as a networked system for a User-Centric Wireless Networks (UCWN). UCWNs allow users to make network connections easily at all times without being conscious of any upgrades or differences in wireless systems. The FWS is a unified wireless platform that simultaneously deals with various types of wireless signals. It consists of flexible access points and a wireless signal processing platform. Various types of wireless signals are received at a distributed flexible access point and transferred to a server in the wireless signal processing platform through the wired access line. Transferred signals are separated and demodulated at the server. To achieve highly flexible and efficient radio wave data transfer between the access point and the server, this paper proposes a sparse-matrix-based compressed sensing method under the framework of the belief propagation and cavity method. Low cost implementation using interlevers and adders is also proposed. An empirical study with real data shows the proposed method achieves greater efficiency and reduced calculation cost compared to the conventional compressed sensing method.

The sparse representation problem of recovering an N dimensional sparse vector x from M1-norm of x under the constraint y = Dx. In this paper, the performance of l1-reconstruction is analyzed, when the dictionary is bi-orthogonal D = [O1O2], where O1, O2are independent and drawn uniformly according to the Haar measure on the group of orthogonal M × M matrices. By an application of the replica method, we obtain the critical conditions under which perfect l1-recovery is possible with bi-orthogonal dictionaries.

We evaluate average error exponent of the undetected error probability of binary matrix ensembles by applying statistical-mechanics approach, which is called the “quenched” average error exponent. In the exixting analysis, the “annealed” average error exponent, which is the error exponent of the average undetected error probability, has been evaluated. The quenched average error exponent is more suitable to capture typical behaviors. We show that there are some cases where the annealed exponent is overestimated for the irregular sparse matrix ensemble. We also show that the quenched average error exponent is equivalent to the annealed average error exponents for the regular sparse matrix ensemble.

We use the replica method of statistical mechanics to examine a typical performance of correctly reconstructing N-dimensional sparse vector x = (xi) from its linear transformation y = Fx of P dimensions on the basis of minimization of the Lp-norm ∥x∥p= lim∈→+0ΣNi=1|xi|p+∈. We characterize the reconstruction performance by the critical relation of the successful reconstruction between the ratio α = P/N and the density ρ of non-zero elements in x in the limit P, N → ∞ while keeping α ~ O(1) and allowing asymptotically negligible reconstruction errors. We show that the critical relation αc(ρ) holds universally as long as FTF can be characterized asymptotically by a rotationally invariant random matrix ensemble and FFTis typically of full rank. This supports the universality of the critical relation observed by Donoho and Tanner (Phil. Trans. R. Soc. A, vol. 367, pp. 4273-4293, 2009; arXiv: 0807.3590) for various ensembles of compression matrices.

We investigate a reconstruction limit of compressed sensing for a reconstruction scheme based on the L1-norm minimization utilizing a correlated compression matrix with a statistical mechanics method. We focus on the compression matrix modeled as the Kronecker-type random matrix studied in research on multiple-input multiple-output wireless communication systems. We found that strong one-dimensional correlations between expansion bases of original information slightly degrade reconstruction performance.

Belief propagation (BP) and the concave convex procedure (CCCP) are both methods that utilize the Bethe free energy as a cost function and solve information processing tasks. We have developed a new algorithm that also uses the Bethe free energy, but changes the roles of the master variables and the slave variables. This is called the Bowman-Levin (BL) approximation in the domain of statistical physics. When we applied the BL algorithm to decode the Gallager ensemble of short-length regular low-density parity check codes (LDPCC) over an additive white Gaussian noise (AWGN) channel, its average performance was somewhat better than that of either BP or CCCP. This implies that the BL algorithm can also be successfully applied to other problems to which BP or CCCP has already been applied

In lossy data compression, the probability that the minimum distortion is larger or smaller than the permissible level for sufficiently large message lengths, when the code rate R is larger or smaller than the rate-distortion function are termed the error exponents. The error exponents can be evaluated from a rigorous assessment. An alternative approach to evaluation using the replica method (RM) developed in statistical mechanics is presented in this paper. This approach shows that codes composed of nonmonotonic perceptrons can provide the optimal exponents with the Hamming distortion, when the transfer function of perceptron is optimized.

We analyze Gallager codes by employing a simple mean-field approxi(cid:173) mation that distorts the model geometry and preserves important interac(cid:173) tions between sites. The method naturally recovers the probability prop(cid:173) agation decoding algorithm as an extremization of a proper free-energy. We find a thermodynamic phase transition that coincides with informa(cid:173) tion theoretical upper-bounds and explain the practical code performance in terms of the free-energy landscape.

Even if it is not possible to reproduce a target input-output relation, a learning machine should be able to minimize the probability of making errors. A practical learning algorithm should also be simple enough to go without memorizing example data, if possible. Incremental algorithms such as error backpropagation satisfy this requirement. We propose incremental algorithms that provide fast convergence of the machine parameter θ to its optimal choice θo with respect to the number of examples t. We will consider the binary choice model whose target relation has a blurred boundary and the machine whose parameter θ specifies a decision boundary to make the output prediction. The question we wish to address here is how fast θ can approach θo, depending upon whether in the learning stage the machine can specify inputs as queries to the target relation, or the inputs are drawn from a certain distribution. If queries are permitted, the machine can achieve the fastest convergence, (θ - θo)2 ∼ O(t−1). If not, O(t−1) convergence is generally not attainable. For learning without queries, we showed in a previous paper that the error minimum algorithm exhibits a slow convergence (θ - θo)2 ∼ O(t−2/3). We propose here a practical algorithm that provides a rather fast convergence, O(t−4/5). It is possible to further accelerate the convergence by using more elaborate algorithms. The fastest convergence turned out to be O[(lnt)2 t−1]. This scaling is considered optimal among possible algorithms, and is not due to the incremental nature of our algorithm.

An objective of machine learning is to find a machine parameter that rxovides the best output prediction for an i~dividual input.For the binary choice problem whose target relation is stochastic, we present art incremental ,.

For the problem of dividing the space originally partitioned by a blurred boundary, every learning algorithm can make the probability of incorrect prediction of an individual example ε decrease with the number of training examples t. We address here the question of how the asymptotic form of ε(t) as well as its limit of convergence reflect the choice of learning algorithms. The error minimum algorithm is found to exhibit rather slow convergence of ε(t) to its lower bound ε0, ε(t) - ε0 ∼ O(t-2/3). Even for the purpose of minimizing prediction error, the maximum likelihood algorithm can be utilized as an alternative. If the true probability distribution happens to be contained in the family of hypothetical functions, then the boundary estimated from the hypothetical distribution function eventually converges to the best choice. Convergence of the prediction error is then ε(t) - ε0 ∼ O(t-1). If the true distribution is not available from the algorithm, however, the boundary generally does not converge to the best choice, but instead ε(t) - ε1 ∼ ±O(t-1/2), where ε1 > ε0 > 0.