Best Subset Selection via a Modern Optimization Lens
透過現代優化鏡頭選擇最佳子集

To overcome the computational difficulties of the best subset problem, computationally tractable convex optimization based methods like Lasso [49, 17] have been proposed as a convex surrogate for Problem (1). For the linear regression problem, the Lagrangian form of Lasso solves
為了克服最佳子集問題的計算困難，基於計算可處理的凸優化的方法（如 Lasso [49, 17]）已被提出作為問題（1）的凸替代。對於線性迴歸問題，Lasso 的拉格朗日形式求解

where the $\ell_{1}$ penalty on $\boldsymbol{\beta}$, i.e., $\|\boldsymbol{\beta}\|_{1}=\sum_{i}|\beta_{i}|$ shrinks the coefficients towards zero and naturally produces a sparse solution by setting many coefficients to be exactly zero. There has been a substantial amount of impressive work on Lasso [23, 15, 5, 55, 32, 59, 19, 35, 39, 53, 50] in terms of algorithms and understanding of its theoretical properties—see for example the excellent books or surveys [11, 34, 50] and the references therein.
其中 $\ell_{1}$ 對 $\boldsymbol{\beta}$ 的懲罰，即 $\|\boldsymbol{\beta}\|_{1}=\sum_{i}|\beta_{i}|$ 將係數縮小到零，並透過將許多係數設為零來自然地產生稀疏解。在演算法和對其理論特性的理解方面，Lasso [23,15,5,55,32,59,19,35,39,53,50] 已經有大量令人印象深刻的工作，例如參見優秀的書籍或調查[11,34,50]以及其中的參考文獻。

Indeed, Lasso enjoys several attractive statistical properties and has drawn a significant amount of attention from the statistics community as well as other closely related fields. Under various conditions on the model matrix $\mathbf{X}$ and $n,p,\boldsymbol{\beta}$ it can be shown that Lasso delivers a sparse model with good predictive performance [11, 34]. In order to perform exact variable selection, much stronger assumptions are required [11]. Sufficient conditions under which Lasso gives a sparse model with good predictive performance are the restricted eigenvalue conditions and compatibility conditions [11]. These involve statements about the range of the spectrum of sub-matrices of $\mathbf{X}$ and are difficult to verify, for a given data-matrix $\mathbf{X}$.
事實上，Lasso 具有幾個有吸引力的統計特性，並引起了統計界以及其他密切相關領域的廣泛關注。在模型矩陣 $\mathbf{X}$ 和 $n,p,\boldsymbol{\beta}$ 的各種條件下，可以證明 Lasso 提供了具有良好預測性能的稀疏模型 [11, 34]。為了執行精確的變數選擇，需要更強的假設[11]。 Lasso 給出具有良好預測性能的稀疏模型的充分條件是受限特徵值條件和相容性條件[11]。這些涉及關於 $\mathbf{X}$ 子矩陣頻譜範圍的陳述，並且對於給定的資料矩陣 $\mathbf{X}$ 很難驗證。

An important reason behind the popularity of Lasso is its computational feasibility and scalability to practical sized problems. Problem (2) is a convex quadratic optimization problem and there are several efficient solvers for it, see for example [44, 23, 29].
Lasso 受歡迎的一個重要原因是它的計算可行性和對實際規模問題的可擴展性。問題（2）是一個凸二次最佳化問題，有幾個有效的解算器，例如參見[44,23,29]。

In spite of its favorable statistical properties, Lasso has several shortcomings. In the presence of noise and correlated variables, in order to deliver a model with good predictive accuracy, Lasso brings in a large number of nonzero coefficients (all of which are shrunk towards zero) including noise variables. Lasso leads to biased regression coefficient estimates, since the $\ell_{1}$-norm penalizes the large coefficients more severely than the smaller coefficients. In contrast, if the best subset selection procedure decides to include a variable in the model, it brings it in without any shrinkage thereby draining the effect of its correlated surrogates. Upon increasing the degree of regularization, Lasso sets more coefficients to zero, but in the process ends up leaving out true predictors from the active set. Thus, as soon as certain sufficient regularity conditions on the data are violated, Lasso becomes suboptimal as (a) a variable selector and (b) in terms of delivering a model with good predictive performance.
儘管 Lasso 具有良好的統計特性，但它也有一些缺點。在有雜訊和相關變數的情況下，為了提供具有良好預測精度的模型，Lasso 引入了大量非零係數（所有係數都縮小到零），包括雜訊變數。套索會導致迴歸係數估計有偏差，因為 $\ell_{1}$ 範數對大係數的懲罰比對小係數的懲罰更嚴重。相反，如果最佳子集選擇過程決定在模型中包含一個變量，它將在沒有任何收縮的情況下將其引入，從而耗盡其相關代理的效果。在增加正規化程度後，Lasso 將更多係數設為零，但在此過程中最終會從活動集中遺漏真正的預測變數。因此，一旦違反了資料上的某些足夠的規律性條件，Lasso 就變得不是最理想的（a）變數選擇器和（b）提供具有良好預測性能的模型。

The shortcomings of Lasso are also known in the statistics literature. In fact, there is a significant gap between what can be achieved via best subset selection and Lasso: this is supported by empirical (for small problem sizes, i.e., $p\leq 30$) and theoretical evidence, see for example, [46, 58, 38, 31, 56, 48] and the references therein. Some discussion is also presented herein, in Section 4.
Lasso 的缺點在統計文獻中也眾所周知。事實上，透過最佳子集選擇和套索可以實現的目標之間存在顯著差距：這是由經驗（對於小問題規模，即 $p\leq 30$ ）和理論證據支持的，例如，參見[ 46、58、38、31、56、48]及其中的參考文獻。本文第 4 節也提出了一些討論。

To address the shortcomings, non-convex penalized regression is often used to “bridge” the gap between the convex $\ell_{1}$ penalty and the combinatorial $\ell_{0}$ penalty [38, 27, 24, 54, 55, 28, 61, 62, 57, 13]. Written in Lagrangian form, this gives rise to continuous non-convex optimization problems of the form:
為了解決這些缺點，通常使用非凸懲罰回歸來「彌合」凸 $\ell_{1}$ 懲罰和組合 $\ell_{0}$ 懲罰之間的差距[38,27,24,54, 55、28 、61、62、57、13]。以拉格朗日形式編寫，這會產生以下形式的連續非凸最佳化問題：

where $p(|\beta|;\gamma;\lambda)$ is a non-convex function in $\beta$ with $\lambda$ and $\gamma$ denoting the degree of regularization and non-convexity, respectively. Typical examples of non-convex penalties include the minimax concave penalty (MCP), the smoothly clipped absolute deviation (SCAD), and $\ell_{\gamma}$ penalties (see for example, [27, 38, 62, 24]). There is strong statistical evidence indicating the usefulness of estimators obtained as minimizers of non-convex penalized problems (3) over Lasso see for example [56, 36, 54, 25, 52, 37, 60, 26]. In a recent paper, [60] discuss the usefulness of non-convex penalties over convex penalties (like Lasso) in identifying important covariates, leading to efficient estimation strategies in high dimensions. They describe interesting connections between $\ell_{0}$ regularized least squares and least squares with the hard thresholding penalty; and in the process develop comprehensive global properties of hard thresholding regularization in terms of various metrics. [26] establish asymptotic equivalence of a wide class of regularization methods in high dimensions with comprehensive sampling properties on both global and computable solutions.
其中 $p(|\beta|;\gamma;\lambda)$ 是 $\beta$ 中的非凸函數， $\lambda$ 和 $\gamma$ 分別表示正規化程度和非凸性程度。非凸懲罰的典型例子包括極小最大凹懲罰（MCP）、平滑剪切絕對偏差（SCAD）和 $\ell_{\gamma}$ 懲罰（例如，參見[27,38,62,24]）。有強有力的統計證據表明，作為非凸懲罰問題 (3) 的最小化器獲得的估計量相對於 Lasso 是有用的，例如 [56,36,54,25,52,37,60,26]。在最近的一篇論文中，[60]討論了非凸懲罰相對於凸懲罰（如 Lasso）在識別重要協變量方面的有用性，從而導致高維度的有效估計策略。他們描述了 $\ell_{0}$ 正則化最小二乘法和具有硬閾值懲罰的最小二乘法之間的有趣聯繫；並在此過程中根據各種指標開發硬閾值正則化的全面全局屬性。 [26]建立了一系列高維正則化方法的漸近等價性，並在全局和可計算解決方案上具有全面的採樣特性。

Problem (3) mainly leads to a family of continuous and non-convex optimization problems. Various effective nonlinear optimization based methods (see for example [62, 24, 13, 36, 54, 38] and the references therein) have been proposed in the literature to obtain good local minimizers to Problem (3). In particular [38] proposes Sparsenet, a coordinate-descent procedure to trace out a surface of local minimizers for Problem (3) for the MCP penalty using effective warm start procedures. None of the existing approaches for solving Problem (3), however, come with guarantees of how close the solutions are to the global minimum of Problem (3).
問題（3）主要導致一系列連續非凸優化問題。文獻中已經提出了各種有效的基於非線性最佳化的方法（例如參見[62,24,13,36,54,38]及其參考文獻）以獲得問題（3）的良好局部最小化器。特別是[38]提出了Sparsenet，一種坐標下降過程，用於使用有效的熱啟動過程來追蹤問題（3）的MCP懲罰的局部最小化器的表面。然而，解決問題（3）的現有方法都無法保證解決方案與問題（3）的全局最小值的接近程度。

The Lagrangian version of (1) given by
(1) 的拉格朗日版本由下式給出

may be seen as a special case of (3). Note that, due to non-convexity, problems (4) and (1) are not equivalent. Problem (1) allows one to control the exact level of sparsity via the choice of $k$, unlike (4) where there is no clear correspondence between $\lambda$ and $k$. Problem (4) is a discrete optimization problem unlike continuous optimization problems (3) arising from continuous non-convex penalties.
可以看作(3)的特例。請注意，由於非凸性，問題 (4) 和 (1) 並不等價。問題(1) 允許人們透過選擇 $k$ 來控制稀疏性的確切級別，這與(4) 不同，其中 $\lambda$ 和 $k$ .問題（4）是離散最佳化問題，與連續非凸懲罰產生的連續最佳化問題（3）不同。

Insightful statistical properties of Problem (4) have been explored from a theoretical viewpoint in [56, 31, 32, 48]. [48] points out that (1) is preferable over (4) in terms of superior statistical properties of the resulting estimator. The aforementioned papers, however, do not discuss methods to obtain provably optimal solutions to problems (4) or (1), and to the best of our knowledge, computing optimal solutions to problems (4) and (1) is deemed as intractable.
[56,31,32,48]從理論角度探討了問題（4）富有洞察力的統計特性。 [48]指出，就所得估計量的優越統計特性而言，（1）優於（4）。然而，上述論文並沒有討論獲得問題（4）或（1）的可證明最優解的方法，並且據我們所知，計算問題（4）和（1）的最優解被認為是棘手的。

The general form of a Mixed Integer Quadratic Optimization (MIQO) problem is as follows:
混合整數二次最佳化 (MIQO) 問題的一般形式如下：

where $\mathbf{a}\in\mathbb{R}^{m},\mathbf{A}\in\mathbb{R}^{k\times m},\mathbf{b}\in\mathbb{R}^{k}$ and $\mathbf{Q}\in\mathbb{R}^{m\times m}$ (positive semidefinite) are the given parameters of the problem; $\mathbb{R}_{+}$ denotes the non-negative reals, the symbol $\boldsymbol{\leq}$ denotes element-wise inequalities and we optimize over $\boldsymbol{\alpha}\in\mathbb{R}^{m}$ containing both discrete ($\alpha_{i},i\in{\mathcal{I}}$) and continuous ($\alpha_{i},i\notin{\mathcal{I}}$) variables, with ${\mathcal{I}}\subset\{1,\ldots,m\}$. For background on MIO see [4]. Subclasses of MIQO problems include convex quadratic optimization problems (${\mathcal{I}}=\emptyset$), mixed integer ($\mathbf{Q}=\mathbf{0}_{m\times m}$) and linear optimization problems ( ${\mathcal{I}}=\emptyset,\mathbf{Q}=\mathbf{0}_{m\times m}$). Modern integer optimization solvers such as Gurobi and Cplex are able to tackle MIQO problems.
其中 $\mathbf{a}\in\mathbb{R}^{m},\mathbf{A}\in\mathbb{R}^{k\times m},\mathbf{b}\in\mathbb{R}^{k}$ 和 $\mathbf{Q}\in\mathbb{R}^{m\times m}$ （正半定）是問題的給定參數； $\mathbb{R}_{+}$ 表示非負實數，符號 $\boldsymbol{\leq}$ 表示逐元素不等式，我們對包含離散 ( $\alpha_{i},i\in{\mathcal{I}}$ ）和連續（ $\alpha_{i},i\notin{\mathcal{I}}$ ）變量，以及 ${\mathcal{I}}\subset\{1,\ldots,m\}$ 。有關 MIO 的背景信息，請參閱 [4]。 MIQO 問題的子類別包括凸二次最佳化問題 ( ${\mathcal{I}}=\emptyset$ )、混合整數 ( $\mathbf{Q}=\mathbf{0}_{m\times m}$ ) 和線性最佳化問題 ( ${\mathcal{I}}=\emptyset,\mathbf{Q}=\mathbf{0}_{m\times m}$ )。現代整數最佳化求解器（例如 Gurobi 和 Cplex）能夠解決 MIQO 問題。

In the last twenty-five years (1991-2014) the computational power of MIO solvers has increased at an astonishing rate. In [7], to measure the speedup of MIO solvers, the same set of MIO problems were tested on the same computers using twelve consecutive versions of Cplex and version-on-version speedups were reported. The versions tested ranged from Cplex 1.2, released in 1991 to Cplex 11, released in 2007. Each version released in these years produced a speed improvement on the previous version, leading to a total speedup factor of more than 29,000 between the first and last version tested (see [7], [42] for details). Gurobi 1.0, a MIO solver which was first released in 2009, was measured to have similar performance to Cplex 11. Version-on-version speed comparisons of successive Gurobi releases have shown a speedup factor of more than 20 between Gurobi 5.5, released in 2013, and Gurobi 1.0 ([7], [42]). The combined machine-independent speedup factor in MIO solvers between 1991 and 2013 is 580,000. This impressive speedup factor is due to incorporating both theoretical and practical advances into MIO solvers. Cutting plane theory, disjunctive programming for branching rules, improved heuristic methods, techniques for preprocessing MIOs, using linear optimization as a black box to be called by MIO solvers, and improved linear optimization methods have all contributed greatly to the speed improvements in MIO solvers [7].
在過去二十五年（1991-2014）中，MIO 求解器的運算能力以驚人的速度成長。在[7]中，為了測量 MIO 求解器的加速，使用 12 個連續版本的 Cplex 在相同的計算機上測試了同一組 MIO 問題，並報告了版本間的加速。測試的版本範圍從1991年發布的Cplex 1.2到2007年發布的Cplex 11。係數超過29,000已測試（詳細資訊請參閱[7]、[42]）。 Gurobi 1.0 是 2009 年首次發布的 MIO 求解器，測量與 CPLEX 11 具有相似的性能。 [7]，[42]）。 1991 年至 2013 年間，MIO 解算器中與機器無關的綜合加速因子為 580,000。這一令人印象深刻的加速係數歸功於將理論和實踐進步融入 MIO 求解器。割平面理論、分支規則的析取編程、改進的啟發式方法、MIO 預處理技術、使用線性優化作為MIO 求解器調用的黑匣子以及改進的線性優化方法都對MIO 求解器的速度提高做出了巨大貢獻。

In addition, the past twenty years have also brought dramatic improvements in hardware. Figure 1 shows the exponentially increasing speed of supercomputers over the past twenty years, measured in billion floating point operations per second [1]. The hardware speedup from 1993 to 2013 is approximately $10^{5.5}\sim 320,000$. When both hardware and software improvements are considered, the overall speedup is approximately 200 billion! Note that the speedup factors cited here refer to mixed integer linear optimization problems, not MIQO problems. The speedup factors for MIQO problems are similar. MIO solvers provide both feasible solutions as well as lower bounds to the optimal value. As the MIO solver progresses towards the optimal solution, the lower bounds improve and provide an increasingly better guarantee of suboptimality, which is especially useful if the MIO solver is stopped before reaching the global optimum. In contrast, heuristic methods do not provide such a certificate of suboptimality.
此外，過去二十年在硬體方面也帶來了巨大的進步。圖 1 顯示了過去二十年來超級電腦的速度呈指數級增長，以每秒十億次浮點運算來衡量 [1]。從 1993 年到 2013 年的硬體加速約為 $10^{5.5}\sim 320,000$ 。同時考慮硬體和軟體改進時，整體加速約 2000 億！請注意，此處引用的加速因子指的是混合整數線性最佳化問題，而不是 MIQO 問題。 MIQO 問題的加速因子類似。 MIO 求解器提供可行的解決方案以及最優值的下限。隨著 MIO 求解器向最優解前進，下界會提高，並為次優性提供越來越好的保證，如果 MIO 求解器在達到全局最優之前停止，這一點尤其有用。相反，啟發式方法不提供這樣的次優證明。

The belief that MIO approaches to problems in statistics are not practically relevant was formed in the 1970s and 1980s and it was at the time justified. Given the astonishing speedup of MIO solvers and computer hardware in the last twenty-five years, the mindset of MIO as theoretically elegant but practically irrelevant is no longer justified. In this paper, we provide empirical evidence of this fact in the context of the best subset selection problem.
人們在 20 世紀 70 年代和 80 年代形成了一種信念，認為 MIO 方法解決統計問題沒有實際意義，並且在當時是有道理的。鑑於 MIO 求解器和電腦硬體在過去 25 年中取得了驚人的加速，MIO 理論上優雅但實際上無關緊要的思維方式不再合理。在本文中，我們在最佳子集選擇問題的背景下提供了這一事實的經驗證據。

We first present a simple reformulation to Problem (1) as a MIO (in fact a MIQO) problem:
我們首先將問題 (1) 重新表述為 MIO（實際上是 MIQO）問題：

where $\mathbf{z}\in\{0,1\}^{p}$ is a binary variable and ${\mathcal{M}}_{U}$ is a constant such that if $\widehat{\boldsymbol{\beta}}$ is a minimizer of Problem (5), then ${\mathcal{M}}_{U}\geq\|\widehat{\boldsymbol{\beta}}\|_{\infty}$. If $z_{i}=1$, then $|\beta_{i}|\leq{\mathcal{M}}_{U}$ and if $z_{i}=0$, then $\beta_{i}=0$. Thus, $\sum_{i=1}^{p}z_{i}$ is an indicator of the number of non-zeros in $\boldsymbol{\beta}$.
其中 $\mathbf{z}\in\{0,1\}^{p}$ 是二元變量， ${\mathcal{M}}_{U}$ 是常數，如果 $\widehat{\boldsymbol{\beta}}$ 是問題 (5) 的最小化，則 ${\mathcal{M}}_{U}\geq\|\widehat{\boldsymbol{\beta}}\|_{\infty}$ 。如果 $z_{i}=1$ ，則 $|\beta_{i}|\leq{\mathcal{M}}_{U}$ ，如果 $z_{i}=0$ ，則 $\beta_{i}=0$ 。因此， $\sum_{i=1}^{p}z_{i}$ 是 $\boldsymbol{\beta}$ 中非零數量的指示符。

Provided that ${\mathcal{M}}_{U}$ is chosen to be sufficently large with ${\mathcal{M}}_{U}\geq\|\widehat{\boldsymbol{\beta}}\|_{\infty}$, a solution to Problem (5) will be a solution to Problem (1). Of course, ${\mathcal{M}}_{U}$ is not known a priori, and a small value of ${\mathcal{M}}_{U}$ may lead to a solution different from (1). The choice of ${\mathcal{M}}_{U}$ affects the strength of the formulation and is critical for obtaining good lower bounds in practice. In Section 2.3 we describe how to find appropriate values for ${\mathcal{M}}_{U}$. Note that there are other MIO formulations, presented herein (See Problem (8)) that do not rely on a-priori specifications of ${\mathcal{M}}_{U}$. However, we will stick to formulation (5) for the time being, since it provides some interesting connections to the Lasso.
假設 ${\mathcal{M}}_{U}$ 選擇足夠大且 ${\mathcal{M}}_{U}\geq\|\widehat{\boldsymbol{\beta}}\|_{\infty}$ ，問題 (5) 的解決方案將是問題 (1) 的解決方案。當然， ${\mathcal{M}}_{U}$ 不是先驗已知的， ${\mathcal{M}}_{U}$ 的較小值可能會導致與（1）不同的解。 ${\mathcal{M}}_{U}$ 的選擇會影響配方的強度，對於在實踐中獲得良好的下限至關重要。在第 2.3 節中，我們描述如何為 ${\mathcal{M}}_{U}$ 找到合適的值。請注意，這裡提出的其他 MIO 公式（請參閱問題 (8)）不依賴 ${\mathcal{M}}_{U}$ 的先驗規範。然而，我們暫時堅持公式（5），因為它提供了與 Lasso 的一些有趣的聯繫。

Formulation (5) leads to interesting insights, especially via the structure of the convex hull of its constraints, as illustrated next:
公式（5）帶來了有趣的見解，特別是透過其約束的凸包結構，如下所示：

Thus, the minimum of Problem (5) is lower-bounded by the optimum objective value of both the following convex optimization problems:
因此，問題 (5) 的最小值受到以下兩個凸優化問題的最佳目標值的下界：

where (7) is the familiar Lasso in constrained form. This is a weaker relaxation than formulation (6), which in addition to the $\ell_{1}$ constraint on $\boldsymbol{\beta}$, has box-constraints controlling the values of the $\beta_{i}$’s. It is easy to see that the following ordering exists: $Z_{3}\leq Z_{2}\leq Z_{1},$ with the inequalities being strict in most instances.
其中 (7) 是熟悉的 Lasso 的約束形式。這是比公式(6) 更弱的鬆弛，公式(6) 除了對 $\boldsymbol{\beta}$ 的 $\ell_{1}$ 約束之外，還具有控制 $\beta_{i}$ 值的框約束' s。很容易看出存在以下順序： $Z_{3}\leq Z_{2}\leq Z_{1},$ ，並且在大多數情況下不等式都是嚴格的。

In terms of approximating the optimal solution to Problem (5), the MIO solver begins by first solving a continuous relaxation of Problem (5). The Lasso formulation (7) is weaker than this root node relaxation. Additionally, MIO is typically able to significantly improve the quality of the root node solution as the MIO solver progresses toward the optimal solution.
就逼近問題（5）的最優解而言，MIO求解器首先求解問題（5）的連續鬆弛。 Lasso 公式 (7) 比根節點鬆弛弱。此外，隨著 MIO 解算器不斷向最優解前進，MIO 通常能夠顯著提高根節點解的品質。

To motivate the reader we provide an example of the evolution (see Figure 2) of the MIO formulation (8) for the Diabetes dataset [23], with $n=350,p=64$ (for further details on the dataset see Section 5).
為了激勵讀者，我們提供了糖尿病數據集[23] 的MIO 公式(8) 演變的示例（參見圖2），其中 $n=350,p=64$ （有關數據集的更多詳細信息，請參見第5節） 。

Since formulation (5) is sensitive to the choice of ${\mathcal{M}}_{U}$, we consider an alternative MIO formulation based on Specially Ordered Sets [4] as described next.
由於公式 (5) 對 ${\mathcal{M}}_{U}$ 的選擇很敏感，因此我們考慮基於特殊有序集 [4] 的替代 MIO 公式，如下所述。

In this section, we obtain estimates for the quantities ${\mathcal{M}}_{U},{\mathcal{M}}_{\ell},{\mathcal{M}}^{\zeta}_{U},{\mathcal{M}}^{\zeta}_{\ell}$ such that an optimal solution to Problem (11) is also an optimal solution to Problem (1), and vice-versa.
在本節中，我們得到數量 ${\mathcal{M}}_{U},{\mathcal{M}}_{\ell},{\mathcal{M}}^{\zeta}_{U},{\mathcal{M}}^{\zeta}_{\ell}$ 的估計，使得問題（11）的最適解也是問題（1）的最適解，反之亦然。

Given a model matrix $\mathbf{X}$, [51] introduced the cumulative coherence function
給定一個模型矩陣 $\mathbf{X}$ ，[51]引入了累積相干函數

where, $\mathbf{X}_{j}$, $j=1,\ldots,p$ represent the columns of $\mathbf{X}$, i.e., features.
其中， $\mathbf{X}_{j}$ 、 $j=1,\ldots,p$ 表示 $\mathbf{X}$ 的列，即特徵。

For $k=1$, we obtain the notion of coherence introduced in  [22, 21] as a measure of the maximal pairwise correlation in absolute value of the columns of $\mathbf{X}$: $\mu:=\mu[1]=\max_{i\neq j}|\langle\mathbf{X}_{i},\mathbf{X}_{j}\rangle|.$
對於 $k=1$ ，我們獲得了 [ 22, 21] 中引入的一致性概念，作為 $\mathbf{X}$ 列絕對值中最大成對相關性的度量： $\mu:=\mu[1]=\max_{i\neq j}|\langle\mathbf{X}_{i},\mathbf{X}_{j}\rangle|.$

[16, 14] (see also [11] and references therein) introduced the notion that a matrix $\mathbf{X}$ satisfies a restricted eigenvalue condition if
[ 16, 14]（另見[ 11]和其中的參考文獻）引入了矩陣 $\mathbf{X}$ 滿足受限特徵值條件的概念，如果

where $\lambda_{\min}(\mathbf{X}_{I}^{\prime}\mathbf{X}_{I})$ denotes the smallest eigenvalue of the matrix $\mathbf{X}_{I}^{\prime}\mathbf{X}_{I}$. An inequality linking $\mu[k]$ and $\eta_{k}$ is as follows.
其中 $\lambda_{\min}(\mathbf{X}_{I}^{\prime}\mathbf{X}_{I})$ 表示矩陣 $\mathbf{X}_{I}^{\prime}\mathbf{X}_{I}$ 的最小特徵值。連接 $\mu[k]$ 和 $\eta_{k}$ 的不等式如下。